Worst-Case and Average-Case Hardness of Hypercycle and Database Problems

Andrea Lincoln; Cheng-Hao Fu; Rene Reyes

REVIEW 3 major objections 5 minor 19 references

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Hypercycle hardness depends on cycle length relative to edge size: short cycles are brute-force hard, longer cycles speed up via matrix multiplication, and random hypergraphs inherit worst-case counting hardness.

desk verdict Real results with a genuine endpoint bug: worth refereeing, but Theorem 1.2 overclaims at k=u. read the letter →

arxiv 2504.18640 v1 pith:TAG26KYN submitted 2025-04-25 cs.CC

Cheng-Hao Fu , Andrea Lincoln , Rene Reyes This is my paper · ORCID

classification cs.CC MSC 05C6568Q1768Q25

keywords fine-grainedcomplexityhypercycledetectionworst-casetoaverage-casereductionsubhypergraphcountingErdős–Rényihypergraphsconjunctivequeryhypercliquehypothesismatrixmultiplication

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Hypercycle problems show a clear phase transition: the time needed to find or count a $k$-hypercycle in a $u$-uniform hypergraph depends on whether the cycle is short relative to the edge size. For short hypercycles, up to roughly $k \le \gamma_3^{-1}(u) \approx 3u/2$, the paper proves under the $(3,k)$-hyperclique hypothesis that near-brute-force time $n^{k-o(1)}$ is necessary. For longer hypercycles, it gives matrix-multiplication-based algorithms that beat brute force, so the hardness genuinely turns at that threshold. On the average-case side, the paper proves that counting any constant-size subhypergraph in an Erdős–Rényi hypergraph is as hard, up to polylog factors, as counting it in a worst-case $k$-partite hypergraph. That transfers the worst-case hypercycle lower bounds to random hypergraphs and to counting queries over random databases.

What carries the argument

The central object is the uniformity transform $\gamma_3(k)=k-\lceil k/3\rceil+1$, which quantifies the smallest edge size needed for a hyperedge to cover any three positions of a $k$-cycle. The paper's self-reducibility lemma shows that in a $k$-circle-layered hypergraph—one whose vertex partitions are arranged on a circle with hyperedges spanning consecutive partitions—any $k$-hypercycle must use exactly one vertex from each partition unless $k$ is a multiple of the edge size; this lets hardness proved at uniformity $\gamma_3(k)$ be lifted to every larger uniformity up to $\gamma_3^{-1}(u)$. On the average-case side, the machinery is a good low-degree polynomial over a prime field whose value equals the subhypergraph count, combined with a recursive inclusion–exclusion procedure that extracts labeled counts from correlated copies of the Erdős–Rényi input, extending the inclusion-edgesclusion technique to hypergraphs with mixed edge sizes.

What would settle it

Find a $k$-circle-layered $u$-uniform hypergraph with $k$ not divisible by $u$ that contains a $k$-hypercycle using two vertices from the same layer; that would disprove Lemma 3.4 and remove the bridge from hyperclique hardness to short-hypercycle hardness. For the average-case claim, exhibit a constant hypergraph $H$ and an algorithm counting $H$ in Erdős–Rényi hypergraphs in $n^{k-\varepsilon}$ time with success probability above the threshold in Theorem 6.1; the reduction would then contradict the $(3,k)$-hyperclique hypothesis by solving #HK faster than $n^{k-o(1)}$.

Watch

Extended reading notes

Core claim

The central claim is that detecting or counting $k$-hypercycles has a complexity phase transition governed by the function $\gamma_3(k)=k-\lceil k/3\rceil+1$. For $k$ in $[u,\gamma_3^{-1}(u)]$, a $u$-uniform $k$-hypercycle is as hard as a $3$-uniform $k$-hyperclique: under the $(3,k)$-hyperclique hypothesis, finding or counting it takes $n^{k-o(1)}$ time. For $k > \gamma_3^{-1}(u)$, three well-separated cycle positions cannot be covered by one hyperedge, so the problem reduces to triangle detection and runs in $n^{k-3+\omega}$ time, and for $k \ge 2u-1$ a second reduction gives $n^{2u-1-(3-\omega)}$ time. In the weighted setting the paper proves matching $n^k$ and $n^{2u-1}$ bounds with the transition at $k=2u-1$. The paper further proves a worst-case-to-average-case reduction: any algorithm counting a constant-size subhypergraph $H$ in Erdős–Rényi hypergraphs with edge probability $1/b$ yields an algorithm of essentially the same runtime for counting $H$ in arbitrary $k$-partite hypergraphs, which makes counting short hypercycles and self-join-free database count queries hard on average under the same hypotheses.

Load-bearing premise

The load-bearing premise is that a $k$-hypercycle in a circularly layered $u$-uniform hypergraph must use exactly one vertex from each layer whenever $k$ is not a multiple of $u$; if a cycle could double back and reuse a layer, the self-reducibility that lifts lower bounds to all larger edge sizes would break.

Editorial extensions

If this is right

Under the $(3,k)$-hyperclique hypothesis, counting $k$-hypercycles in $u$-uniform hypergraphs requires $n^{k-o(1)}$ time for every $k$ in $[u,\gamma_3^{-1}(u)]$, and this lower bound transfers to counting in Erdős–Rényi hypergraphs.
The brute-force lower bound cannot extend past $\gamma_3^{-1}(u)$: the paper's triangle-detection algorithm solves $k$-hypercycle in $n^{k-3+\omega}$ time, so any stronger lower bound would imply a lower bound on fast matrix multiplication.
For minimum-weight hypercycles, the matching upper and lower bounds give a complete picture: $n^k$ for $k$ in $[u+1,2u-1]$ and $n^{2u-1}$ for longer cycles.
Counting any constant-size subhypergraph in random hypergraphs is as hard as counting it in the worst case, so every future worst-case detection lower bound for a hypergraph substructure automatically becomes an average-case counting lower bound.
Self-join-free conjunctive count queries on random databases inherit worst-case hardness, while the paper's appendix notes that the corresponding enumeration and decision tasks are easy on average.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Although the paper states the worst-case-to-average-case reduction for subhypergraph counting, an implicit consequence is that any future fine-grained lower bound for detecting a constant-size hypergraph pattern immediately yields an average-case lower bound for counting that pattern, so the reduction is a general transfer tool rather than a hypercycle-specific result.
The unresolved window $k$ in $(\gamma_3^{-1}(u), 2u-2)$ invites a smoothed dichotomy: the true exponent may be $\min(k, k-3+\omega, 2u-1)$, and closing that window would require new reductions that interpolate between triangle detection and reachability-based methods.
For practical database systems, the paper implies COUNT queries remain hard on uniformly random data while simple enumeration is easy, suggesting query optimizers should treat counting and enumeration as genuinely different cost profiles.
A testable extension is to tighten the success-probability threshold in Theorem 6.1; the $b^{-2^k}$ factor comes from the labeled-recursion analysis and may be improvable without changing the core reduction.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this paper has real content—the weighted hypercycle bounds are tight, the unweighted phase-transition story is new, and the worst-case-to-average-case reduction for mixed-size subhypergraphs is a genuine extension of DLW20. But Theorem 1.2 as stated is false at k=u, and the text needs a cleanup pass.

The weighted results are the cleanest: matching n^{k-o(1)} bounds for k in [u+1, 2u-1] and an algorithm for longer cycles that runs in O(n^{2u-1}) regardless of k. The unweighted results introduce the k-circle-layered self-reducibility trick and a matrix-multiplication speedup at the phase transition; those are worth the price of admission. The average-case reduction handles hyperedges of different sizes and gives the database count-query application, which is a nice bridge between fine-grained complexity and database theory.

The soft spots are real. The endpoint k=u of Theorem 1.2 is not covered by the proof: the claim that k ≤ γ3^{-1}(u) < 2u implies k is not a multiple of u is false at k=u, and Lemma 3.5 explicitly requires k not ≡ 0 mod u. The stress-test example works—a single 3-edge (v0,v1,v2) in a 4-circle-layered 3-uniform graph has no 4-hypercycle, but the constructed 4-uniform graph contains the spurious 4-hypercycle (v0,v1,v2,v3). At k=u the problem is trivial (one hyperedge), so this is a genuine overclaim. The theorem and Corollary 3.6 should exclude k=u or handle it separately.

Beyond that, the paper is sloppier than it should be: Definition 5 defines hypercycle as hyperclique, lower bounds are written with O instead of Ω in several places, Lemma 3.5's edge-count formula is wrong (|E'| = |E|·n^{u-u'}, not |E|^{u-u'}), and Theorem 6.1 says "k = O(1) edges" where it means "e = O(1) edges". None of these are load-bearing once fixed, but together they make verification harder than it needs to be.

The citation pattern is fine: the LWW18 and DLW20 theorems are published prior work, and using them black-box is legitimate. I didn't find circularity. The core reductions and algorithms look plausible; the average-case inclusion-exclusion is intricate but I saw no hole beyond the endpoint issue.

I'd send this to a serious referee. The contributions justify the time, and the main flaw is fixable. My recommendation: engage with it, but require the authors to correct Theorem 1.2 before publication.

Referee Report

3 major / 5 minor

Summary. The paper studies the fine-grained complexity of k-hypercycles in u-uniform hypergraphs and of counting subhypergraphs in average-case instances. It claims tight n^{k-o(1)} lower bounds for minimum-weight k-hypercycle for k in [u+1,2u-1] under the minimum-k-clique hypothesis; tight n^{k-o(1)} lower bounds for unweighted k-hypercycle for k in [u, gamma_3^{-1}(u)] under the (3,k)-hyperclique hypothesis; algorithms beating brute force for longer hypercycles, with the best runtime O(n^{2u-1-(3-omega)}) for k >= 2u-1; and a worst-case-to-average-case reduction showing that counting small subhypergraphs in Erdős-Rényi hypergraphs is as hard as counting in the worst case, with applications to self-join-free count queries in databases.

Significance. If the results are correct, the paper makes a substantial advance: it gives the first tight fine-grained bounds for hypercycle problems that depend on both cycle length and uniformity, extends the Dalirrooyfard-Lincoln-Williams average-case machinery from graphs to hypergraphs with mixed edge sizes, and connects fine-grained average-case hardness to database count queries. The reductions are built on published hypotheses and on the prior theorems of LWW18 and DLW20, with no fitted parameters. Many proofs are supplied in detail, and the statement of Lemma 6.9 is accompanied by a full proof in Appendix A.1. The proposed worst-case-to-average-case chain, if valid, is a useful contribution in its own right.

major comments (3)

[Section 3.2.3, Theorem 1.2 and Lemma 3.5] Theorem 1.2 states a lower bound for k in [u, gamma_3^{-1}(u)], but the proof explicitly invokes Lemma 3.5, which requires k not congruent to 0 mod u. The assertion in the proof that k <= gamma_3^{-1}(u) < 2u implies k is not a multiple of u is false when k = u. For example, u = 4 gives gamma_3^{-1}(4) = 5, so k = 4 lies in the stated range and is a multiple of 4. At k = u a u-hypercycle is a single hyperedge, so the claimed n^{u-o(1)} lower bound is not a consequence of the (3,u)-hyperclique hypothesis and is false for sparse inputs. Moreover, the reduction in Lemma 3.5 genuinely creates spurious hypercycles at this endpoint: a 4-circle-layered 3-uniform graph containing only the edge (v0,v1,v2) maps to a 4-uniform graph containing the single 4-edge (v0,v1,v2,v3), which is itself a 4-hypercycle. Theorem 1.2 and Corollary 3.6 must exclude k = u or handle it by a separate argument.
[Section 3.2.1, Lemma 3.4] Lemma 3.4 is load-bearing for the self-reducibility Lemma 3.5, but its proof is not rigorous as written. The claim that every hyperedge of the cycle contains exactly one vertex from a partition whose label is a multiple of u is asserted without justification for cycles that use a partition more than once, and the induction proving v_{au} in V_{ru} is unclear. Since the whole extension from uniformity gamma_3(k) to larger u depends on ruling out 'backward cycles,' the lemma needs a complete, careful proof; alternatively the extension should be proven by a different argument that does not rely on this structural claim.
[Section 5.2.3, Lemma 5.11 and Theorem 1.1] Lemma 5.11 is used to transfer minimum-hypercycle hardness from uniformity u to larger uniformity u', but the proof only discusses existence and counting of hypercycles and never assigns weights to the extended hyperedges in the constructed graph G'. Since Theorem 1.1 is a lower bound for the minimum-weight k-hypercycle problem, the reduction must specify the weights of the n^{u'-u} extensions and prove that minimum-weight k-hypercycles in G' correspond exactly to minimum-weight k-hypercycles in G. Without this, the lower-bound transfer for the weighted problem is incomplete.

minor comments (5)

[Section 2, Definition 5] Definition 5 defines a k-hypercycle as a hyperclique on k vertices, while the surrounding text says that the paper uses 'k-hypercycle' to mean the tight hypercycle of Definition 4. Having two contradictory definitions is confusing and should be corrected, for example by deleting Definition 5 or renaming it.
[Theorem 1.2 and Corollary 3.6] Lower bounds are written as 'requires O(n^{k-o(1)}) time,' which is the wrong asymptotic notation; they should read Omega(n^{k-o(1)}).
[Section 3.2.2, Lemma 3.5] The edge-count formula |E'| = |E|^{u-u'} is dimensionally wrong and should be |E| times the number of choices of extension vertices, i.e., at most |E| n^{u-u'} (or the appropriate product of partition sizes).
[Section 6.4, Theorem 6.1] The statement says 'Let H have e edges and k = O(1) edges' and 'counting subgraphs A in Erdős-Rényi hypergraphs'; the first should be 'k = O(1) vertices' and the second should refer to H, not A.
[Section 5.1.3, Lemma 5.4] The success-amplification text says the procedure is repeated '10 + 10 k^{-k}' times, but later the runtime bound uses '10 + 10 k^k' repetitions; the former is inconsistent with the claimed 2/3 success probability and should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower-bound and average-case chains rest on published prior theorems and explicit constructions, not on restatements of the target claims.

full rationale

I walked the derivation chain from Theorem 1.2 through Theorem 6.1. The short-hypercycle lower bound is: assume the (3,k)-hyperclique hypothesis, apply the LWW18 reduction (quoted as Theorem 2.1) to get hardness of (gamma_3(k),k)-hypercycle, then use monotonicity of gamma_3 (Lemma 3.2) and the self-reducibility lemma (Lemma 3.5) to lift the hardness to uniformity u. Theorem 2.1 is a published, parameter-free reduction whose stated assumptions do not include the paper's target results; it is a real external theorem, not a restatement of the conclusion. Lemma 3.5 is proved in the text by an explicit extension construction, with the no-spurious-cycles direction justified by Lemma 3.4; it is not defined in terms of the desired hardness. The average-case chain (#HK to #H to U#H to #HER) uses the good-low-degree-polynomial framework: the polynomial f is explicitly constructed in Lemma 6.2, its goodness is proved in Lemma 6.3, and Theorem 6.4 is quoted from the published DLW20 paper. The recursion, inclusion-exclusion, and labeling steps (Lemmas 6.7-6.12) are argued in the text and appendix. No fitted parameter is renamed as a prediction, and no equation is true by construction of its own input. The skeptical k=u endpoint is a genuine correctness concern: Lemma 3.5 requires k not congruent to 0 mod u, and in the proof of Theorem 1.2 the sentence 'k <= gamma_3^{-1}(u) < 2u so it is not a multiple of u' is false when k=u, so the stated lower bound is not established at that endpoint. However, this is a mathematical edge-case gap, not circularity: the argument is not equivalent to its inputs. The load-bearing citations to LWW18 and DLW20 share a coauthor with the present paper, but per the rules this does not raise the circularity score because those results are published, checkable theorems with assumptions independent of the target claims.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The theorems are conditional on two unproved conjectures plus accepted prior theorems from LWW18 and DLW20 used as black boxes. All runtimes assume constant pattern size. There are no fitted numerical parameters and no newly postulated physical or mathematical entities.

assumptions (6)

domain assumption Minimum k-clique hypothesis (Definition 1): finding a min-weight k-clique on a Word-RAM requires n^{k-o(1)} time.
Used as the basis for the min-weight hypercycle lower bounds in Section 5.2. It is a conjecture, not a proven theorem.
domain assumption (3,k)-hyperclique hypothesis (Definition 2): finding a k-hyperclique in a 3-uniform hypergraph requires n^{k-o(1)} time for k > 3.
Basis for the unweighted short-hypercycle lower bounds in Theorem 1.2. It is an unproved fine-grained hypothesis.
standard math Theorem 2.1, repeated from LWW18: the hyperclique-to-hypercycle reduction preserves vertex count and, in the weighted case, minimum weights.
Used as a black box in the lower-bound proofs and to define γ_u(k). This is a published prior theorem from SODA 2018.
standard math Theorem 6.4, repeated from DLW20: a good low-degree polynomial for a problem gives a worst-case-to-average-case reduction.
Used to convert average-case algorithms for U#H and USCQ into worst-case algorithms. This is a published theorem from FOCS 2020.
standard math Color-coding lemma from LWW18: an algorithm on k-circle-layered hypergraphs implies an algorithm on arbitrary hypergraphs with k^k overhead.
Used in Theorems 1.3 and 5.5 to remove the layered structure assumption. It is an accepted prior result.
domain assumption Constant parameter regime: k = O(1), u constant, so k^k, b^{2^k}, and 2^{2^k} are constant factors.
The stated runtimes and average-case reductions become polynomial only in this regime; the paper does not treat k or u growing with n.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Worst-Case and Average-Case Hardness of Hypercycle and Database Problems." pith.science (2026). https://pith.science/paper/TAG26KYN

@misc{pith2026250418640,
  author       = {Pith},
  title        = {Pith review of: Worst-Case and Average-Case Hardness of Hypercycle and Database Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TAG26KYN}},
  note         = {Machine review of arXiv:2504.18640}
}

read the original abstract

In this paper we present tight lower-bounds and new upper-bounds for hypergraph and database problems. We give tight lower-bounds for finding minimum hypercycles. We give tight lower-bounds for a substantial regime of unweighted hypercycle. We also give a new faster algorithm for longer unweighted hypercycles. We give a worst-case to average-case reduction from detecting a subgraph of a hypergraph in the worst-case to counting subgraphs of hypergraphs in the average-case. We demonstrate two applications of this worst-case to average-case reduction, which result in average-case lower bounds for counting hypercycles in random hypergraphs and queries in average-case databases. Our tight upper and lower bounds for hypercycle detection in the worst-case have immediate implications for the average-case via our worst-case to average-case reductions.

Figures

Figures reproduced from arXiv: 2504.18640 by the authors.

**Figure 1.** The running time of minimum weight hyper-cycle in a weighted u-uniform hyper-graph. The exponent of the running time is indicated by the black line and the lower bound is matching, as indicated by the hatched red area. Note the running time is O(n u ) for a u length hyper-cycle and O(n 2u−1 ) for a 2u−1 length hyper-cycle. Then for all hyper-cycles of length k > 2u−1 the running time continues to be O(n 2u−1 ). cove… view at source ↗

**Figure 2.** The running time of unweighted hyper-cycle in a u-uniform hyper-graph. The exponent of the running time is indicated by the black line. The lower bound is matching for the hatched red area from cycles of length u to γ −1 3 (u) and the running time is O(n k ) for a k-hypercycle. Then from γ −1 3 (u) to 2u−1 the running time is O˜(n k−3+ω) for k-hypercycle where ω is the matrix multiplication constant (ω < 2.3716 [WXX… view at source ↗

**Figure 3.** An example of a small subgraph with hyperedges of multiple different sizes. This graph contains hyperedges {A,B},{B,C},{B,D},{C,D},{A,B,C}, and {B,C,D,E}. We depict the 3-width edge as a red circle, the 4-width edge as a blue circle, and the 2-width edges as black lines. copies of H where vi ∈ Vi can be solved with polylog calls to a counter for hypergraphs H in uniformly random hypergraphs. Via color-coding this me… view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: An example of two small graphs and corresponding H-partite graphs. In this paper we use the term k-hypercycle to refer to a tight k-hypercycle. We use these concepts throughout the paper. We also use a more general notion of a subgraph of a hypergraph. Definition 6. A …

**Figure 5.** Figure 5: The case of k = 7 where we start with a 3-uniform graph. The double circles indicate the ‘farthest apart’ three nodes can be. Note the purple and blue arcs indicate the furthest a uniformity 4 hyperedge can go while including the top node, and that neither hyperedge in…

**Figure 6.** Figure 6: Example with uniformity u = 3 to demonstrate why you need u−1 nodes. These are the four hyperedges which involve only the vertices v1, v2, v2, vk , vk−1, and vk−2. The two thick hyperedges include at least one vertex from v1, v2, v3 and at least one vertex from vk , vk…

**Figure 7.** Figure 7: The (u, k)-ECLR problem. Definition 11. (Weighted) (k,u)-extension uniform circle-layered reachability problem ((Weighted) (u, k)-ECLR) Let G = (V,E) be an n-vertex u-uniform k-circle-layered (weighted) hypergraph with vertex 17 [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages

[1]

Tight cycles in hypergraphs

Peter Allen, Julia B \"o ttcher, Oliver Cooley, and Richard Mycroft. Tight cycles in hypergraphs. Electronic Notes in Discrete Mathematics , 49:675--682, 2015

work page 2015
[2]

Finding tight hamilton cycles in random hypergraphs faster

Peter Allen, Christoph Koch, Olaf Parczyk, and Yury Person. Finding tight hamilton cycles in random hypergraphs faster. In Michael A. Bender, Martin Farach - Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings , volume 10807 of Lecture Notes i...

work page 2018
[3]

Consequences of faster alignment of sequences

Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I , volume 8572 of Lectu...

work page 2014
[4]

The average-case complexity of counting cliques in erd o s-r \' e nyi hypergraphs

Enric Boix - Adser \` a , Matthew Brennan, and Guy Bresler. The average-case complexity of counting cliques in erd o s-r \' e nyi hypergraphs. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 , pages 1256--1280. IEEE Computer Society, 2019

work page 2019
[5]

Tight fine-grained bounds for direct access on join queries

Karl Bringmann, Nofar Carmeli, and Stefan Mengel. Tight fine-grained bounds for direct access on join queries. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , PODS '22, page 427–436, New York, NY, USA, 2022. Association for Computing Machinery

work page 2022
[6]

Average-case fine-grained hardness

Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 483--496. ACM , 2017

work page 2017
[7]

Proofs of work from worst-case assumptions

Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Proofs of work from worst-case assumptions. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I , volume 10991 of Lecture Notes in Com...

work page 2018
[8]

Improving viterbi is hard: Better runtimes imply faster clique algorithms

Arturs Backurs and Christos Tzamos. Improving viterbi is hard: Better runtimes imply faster clique algorithms. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017 , volume 70 of Proceedings of Machine Learning Research , pages 311--321. PMLR , 2017

work page 2017

Show all 19 references

[9]

On the enumeration complexity of unions of conjunctive queries

Nofar Carmeli and Markus Kr\" o ll. On the enumeration complexity of unions of conjunctive queries. ACM Trans. Database Syst. , 46(2), may 2021

2021
[10]

Conjunctive queries with self-joins, towards a fine-grained enumeration complexity analysis

Nofar Carmeli and Luc Segoufin. Conjunctive queries with self-joins, towards a fine-grained enumeration complexity analysis. In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , PODS '23, page 277–289, New York, NY, USA, 2023. Associ...

2023
[11]

Tractable orders for direct access to ranked answers of conjunctive queries

Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer, Benny Kimelfeld, and Mirek Riedewald. Tractable orders for direct access to ranked answers of conjunctive queries. ACM Trans. Database Syst. , 48(1):1:1--1:45, 2023

2023
[12]

New techniques for proving fine-grained average-case hardness

Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams. New techniques for proving fine-grained average-case hardness. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Virtual, November 16 – 19, 2020 . IEEE Computer Society, 2020

2020
[13]

On counting t -cliques mod 2

Oded Goldreich. On counting t -cliques mod 2. Electron. Colloquium Comput. Complex. , TR20-104 , 2020

2020
[14]

On tight cycles in hypergraphs

Hao Huang and Jie Ma. On tight cycles in hypergraphs. SIAM Journal on Discrete Mathematics , 33(1):230--237, 2019

2019
[15]

Ryan Williams

Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, Janua...

2018
[16]

Fine-grained complexity, logic, and query evaluation program

Hung Ngo, Kirk Pruhs, Atri Rudra, and Virginia Vassilevska Williams. Fine-grained complexity, logic, and query evaluation program. Simons Institute for the Theory of Computing, Workshop Schedule, September 2023. Logic and Algorithms in Database Theory and AI

2023
[17]

Free join: Unifying worst-case optimal and traditional joins

Yisu Remy Wang, Max Willsey, and Dan Suciu. Free join: Unifying worst-case optimal and traditional joins. Proc. ACM Manag. Data , 1(2):150:1--150:23, 2023

2023
[18]

New bounds for matrix multiplication: from alpha to omega

Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. CoRR , abs/2307.07970, 2023

2023 arXiv
[19]

u cken, Germany (Virtual Conference) , series = LIPIcs , volume = 168 , publisher = Schloss Dagstuhl - Leibniz-Zentrum f \

alpha my Discussion sec:appendix_discussion discussion document my.bib0000664000000000000000000017542615002752266010705 0ustar rootroot@article kroll2021, author = Carmeli, Nofar and Kr\" o ll, Markus , title = On the Enumeration Complexity of Unions of Conjunctive Queries , y...

2021

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

Tight cycles in hypergraphs

Peter Allen, Julia B \"o ttcher, Oliver Cooley, and Richard Mycroft. Tight cycles in hypergraphs. Electronic Notes in Discrete Mathematics , 49:675--682, 2015

work page 2015

[2] [2]

Finding tight hamilton cycles in random hypergraphs faster

Peter Allen, Christoph Koch, Olaf Parczyk, and Yury Person. Finding tight hamilton cycles in random hypergraphs faster. In Michael A. Bender, Martin Farach - Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings , volume 10807 of Lecture Notes i...

work page 2018

[3] [3]

Consequences of faster alignment of sequences

Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I , volume 8572 of Lectu...

work page 2014

[4] [4]

The average-case complexity of counting cliques in erd o s-r \' e nyi hypergraphs

Enric Boix - Adser \` a , Matthew Brennan, and Guy Bresler. The average-case complexity of counting cliques in erd o s-r \' e nyi hypergraphs. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 , pages 1256--1280. IEEE Computer Society, 2019

work page 2019

[5] [5]

Tight fine-grained bounds for direct access on join queries

Karl Bringmann, Nofar Carmeli, and Stefan Mengel. Tight fine-grained bounds for direct access on join queries. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , PODS '22, page 427–436, New York, NY, USA, 2022. Association for Computing Machinery

work page 2022

[6] [6]

Average-case fine-grained hardness

Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 483--496. ACM , 2017

work page 2017

[7] [7]

Proofs of work from worst-case assumptions

Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Proofs of work from worst-case assumptions. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I , volume 10991 of Lecture Notes in Com...

work page 2018

[8] [8]

Improving viterbi is hard: Better runtimes imply faster clique algorithms

Arturs Backurs and Christos Tzamos. Improving viterbi is hard: Better runtimes imply faster clique algorithms. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017 , volume 70 of Proceedings of Machine Learning Research , pages 311--321. PMLR , 2017

work page 2017