{"id":"ade8990d-309b-4fd0-b9b9-4e13c7f6bdce","arxiv_id":"2504.18640","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Short hypercycles require brute force under hyperclique hypotheses, longer cycles admit matrix-multiplication speedups, and counting subhypergraphs or database query answers on random data is as hard as the corresponding worst-case counting.","lead":"This paper proves tight conditional lower bounds and matching algorithms for finding and counting hypercycles, and shows that counting small subhypergraphs in random hypergraphs is as hard as detecting them in the worst case. The same reduction gives average-case hardness for self-join-free counting queries in random databases.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2 fails at k=u: the proof's claim that k is not a multiple of u is false, and Lemma 3.5's extension creates spurious hypercycles at this endpoint.","rationale":"The paper's central contribution includes tight lower bounds for short unweighted hypercycles, with Theorem 1.2 stated for the full range k in [u, gamma_3^{-1}(u)]. The reader correctly identified Lemma 3.4/3.5 and the k=u multiple-of-u case as a weak point. My reading sharpens this: at k=u the proof's exclusion of multiples of u is plainly false, and the construction in Lemma 3.5 demonstrably creates spurious hypercycles, as shown by the single-3-edge counterexample. This is a concrete correctness issue in a stated theorem, not just a missing proof detail. However, the failure is confined to the boundary case k=u: for k>u in the stated range, k is not a multiple of u, and Lemma 3.4's exact-one-vertex-per-partition conclusion appears plausible, so the lower-bound framework may survive with the range corrected to k in [u+1, gamma_3^{-1}(u)] or with a separate argument for k=u. The average-case corollary inherits the same boundary problem, since counting single hyperedges in random hypergraphs is trivial or input-size-bound rather than a genuine fine-grained hardness result. I therefore recommend a conditional acceptance: the authors should fix the range and the proof of Theorem 1.2, or explicitly handle k=u, before the stated results can be taken at face value. I do not see an independent fatal flaw in the matrix-multiplication algorithms or in the high-level structure of the worst-case-to-average-case reduction, though those parts also contain numerous notational slips that a revision should clean up.","tokens_in":35158,"tokens_out":43223,"duration_ms":426801,"concrete_test":"Run the Lemma 3.5 construction on the concrete instance with k=4, u'=3, u=4: take partitions V0,...,V3, and let G be the 4-circle-layered 3-uniform hypergraph with exactly one hyperedge (v0,v1,v2), v_i in V_i. Verify (1) G contains no 4-hypercycle, because a 4-hypercycle needs all four triples (v0,v1,v2), (v1,v2,v3), (v2,v3,v0), (v3,v0,v1), only one of which is present; and (2) the u-uniform extension G' contains the 4-edge (v0,v1,v2,v3), which is a 4-hypercycle. This settles that the self-reduction creates new hypercycles when k is a multiple of u. Additionally, re-examine the proof of Theorem 1.2 with k=u and u=4 to confirm that the assertion 'k <= gamma_3^{-1}(u) < 2u so it is not a multiple of u' is false. If the intended range is k in [u+1, gamma_3^{-1}(u)], check that every k in this range is not a multiple of u and that Lemma 3.4 then applies.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The short-hypercycle lower bound Theorem 1.2 is stated for k in [u, gamma_3^{-1}(u)] and underpins Corollary 3.6. The endpoint k=u lies in this range for many u (e.g., u=4 gives gamma_3^{-1}(4)=5), but the proof asserts that k <= gamma_3^{-1}(u) < 2u implies k is not a multiple of u, which is false when k=u. Lemma 3.5, the self-reducibility step that lifts hardness from uniformity gamma_3(k) to u, explicitly requires k not congruent to 0 mod u, so it cannot be applied at k=u. This is not merely a missing case; the reduction genuinely fails. For u'=3, k=4, take a 4-circle-layered 3-uniform graph G with one hyperedge (v0,v1,v2), where v_i in V_i. G contains no 4-hypercycle, since a 4-hypercycle would require the four triples (v0,v1,v2), (v1,v2,v3), (v2,v3,v0), (v3,v0,v1), and only the first exists. The Lemma 3.5 construction adds every 4-edge (v0,v1,v2,w) with w in V3, so the constructed 4-uniform graph G' contains the single 4-edge (v0,v1,v2,v3), which is a 4-hypercycle. Thus G' has a spurious hypercycle that does not correspond to any hypercycle in G. At k=u a u-hypercycle is just one hyperedge, so the claimed n^{u-o(1)} lower bound is at best trivial for dense inputs and false for sparse inputs; in any case it is not established from the (3,u)-hyperclique hypothesis. The theorem and Corollary 3.6 should exclude k=u or treat it separately.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":35546,"tokens_out":10254,"duration_ms":98875,"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":[{"comment":"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":"Section 3.2.3, Theorem 1.2 and Lemma 3.5"},{"comment":"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":"Section 3.2.1, Lemma 3.4"},{"comment":"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.","section":"Section 5.2.3, Lemma 5.11 and Theorem 1.1"}],"minor_comments":[{"comment":"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.","section":"Section 2, Definition 5"},{"comment":"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":"Theorem 1.2 and Corollary 3.6"},{"comment":"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":"Section 3.2.2, Lemma 3.5"},{"comment":"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":"Section 6.4, Theorem 6.1"},{"comment":"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.","section":"Section 5.1.3, Lemma 5.4"}],"recommendation":"major_revision","confidential_remarks":"The main reason for major revision rather than rejection is that the k = u endpoint of Theorem 1.2 appears to be a genuine false statement, but it might be fixable by excluding k = u from the theorem and adjusting Corollary 3.6 and Figure 2 accordingly. The reliance on LWW18 and DLW20, both sharing a coauthor, is standard and those results are published and checkable, so I do not see a circularity problem. The authors should also tighten Lemma 3.4 and complete the weighted transfer in Lemma 5.11 before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nBeyond 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.\n\nThe 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.\n\nI'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.","headline":"Real results with a genuine endpoint bug: worth refereeing, but Theorem 1.2 overclaims at k=u.","tokens_in":36077,"tokens_out":5941,"would_cite":true,"duration_ms":56680,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["fine-grained complexity","hypercycle detection","worst-case to average-case reduction","subhypergraph counting","Erdős–Rényi hypergraphs","conjunctive query counting","hyperclique hypothesis","matrix multiplication"],"falsifier":"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)}$.","tokens_in":34936,"feed_emoji":"🔁","tokens_out":10516,"duration_ms":91228,"temperature":0.7,"pith_summary":"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.","feed_headline":"Hypercycle hardness hinges on cycle length vs edge size","feed_subtitle":"Short cycles are brute-force hard; longer cycles speed up, and random hypergraphs inherit worst-case hardness.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the hyperclique-to-hypercycle reduction and the circle-layered color-coding lemma that turn arbitrary hypergraphs into layered ones","marker":"[LWW18]"},{"why":"provides the good low-degree polynomial framework and the worst-case-to-average-case reduction theorem that the hypergraph extension builds on","marker":"[DLW20]"},{"why":"introduced the average-case fine-grained hardness technique based on error-correcting properties of low-degree polynomials","marker":"[BRSV17]"},{"why":"established worst-case/average-case equivalence for counting constant-size hypercliques in Erdős–Rényi hypergraphs, the result generalized to arbitrary subhypergraphs","marker":"[BBB19]"},{"why":"states the min-weight $k$-clique hypothesis used for the weighted hypercycle lower bounds","marker":"[AWW14]"},{"why":"also cited as a source of the min-weight $k$-clique hypothesis used in the weighted lower-bound arguments","marker":"[BT17]"},{"why":"supplies the current matrix multiplication exponent $\\omega<2.3716$ used in the stated algorithm runtimes","marker":"[WXXZ23]"}],"fun_headline_variants":["Hypercycle complexity shifts with cycle length vs edge size","Counting hypercycles on average is as hard as worst-case","Short hypercycles need brute force; long ones get fast methods","Hypercycle detection: tight bounds reveal a phase transition","Worst-case hardness transfers to counting hypercycles randomly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hypercycle complexity shifts with cycle length vs edge size","Counting hypercycles on average is as hard as worst-case","Short hypercycles need brute force; long ones get fast methods","Hypercycle detection: tight bounds reveal a phase transition","Worst-case hardness transfers to counting hypercycles randomly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000331,"raw_usage":{"total_tokens":1864,"prompt_tokens":986,"completion_tokens":878,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":602,"completion_tokens_details":{"reasoning_tokens":799}},"tokens_in":602,"tokens_out":878,"duration_ms":8306,"temperature":1.0,"reasoning_tokens":799,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:14:27.100761+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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)}$.","supporting_citations":[],"review_version":1}