{"id":"82e2be5d-6575-4a7b-a020-2ec047faeda9","arxiv_id":"2602.17834","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Listing all 3-way loops in an r-uniform hypergraph takes Θ(n^{r−5/3}/log n) rounds in the congested-clique and primal-congest models, with density-parameterized algorithms for sparse and everywhere-sparse hypergraphs.","lead":"Distributed triangle listing in hypergraphs was open; this paper defines six communication models for group edges and gives matching upper and lower round bounds in the two strongest models. It also introduces a density measure for hypergraphs that may generalize arboricity-based distributed algorithms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main CLIQUE/PC lower bound rests on an imported, unproved information inequality (Lemma 3.20) applied to a data-dependent max vertex.","rationale":"I focused on Lemma 3.20 rather than the Theorem 4.4 reduction issue because the former is the load-bearing condition for the paper's strongest claim: matching upper and lower bounds for triangle enumeration in the CLIQUE and PRIMAL CONGEST models. The reader independently identified Lemma 3.20 as the weakest assumption, and my reading confirms that this is where the proof is least secure. The concern is not that the lemma is known to be false; it is that it is unverified in the hypergraph setting and is applied in a way (to a data-dependent max vertex) that is not justified. These are fixable by supplying the missing proof and a correct averaging argument, so the verdict should remain CONDITIONAL rather than moving to ACCEPT or REJECT. I did not see a reason to change the reader's conditional assessment; the other issues noted by the reader (Theorem 4.4 reduction, incomplete proof statements, TODO) are secondary and also fixable.","tokens_in":32566,"tokens_out":29433,"duration_ms":308353,"concrete_test":"Obtain the full proof of Izumi and Le Gall's Lemma 4.3 and transcribe every step for r-uniform hypergraphs, checking specifically (a) the step H(E(T_v)) ≥ E[|E(T_v)|] and (b) any use of the fact that v is a fixed vertex. Then reformulate the end of the proof of Theorem 3.3 replacing the data-dependent w by a fixed vertex with an explicit averaging argument, and compute the resulting lower bound. If the transcription fails or the averaging loses a factor of n, the claimed Ω(n^{r−5/3}/log n) lower bound is not established. As a small empirical supplement, enumerate all 2^10 inputs for n=5, r=3 with the lexicographic triangle partition and verify the inequality for each vertex; a counterexample would immediately refute Lemma 3.20.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central optimality claim, Theorem 3.3, depends on Lemma 3.20, which is imported from Izumi and Le Gall with the comment that the proof is identical and is not reproduced. The lemma asserts I(E;T_v) ≥ E[|E(T_v)|] for every vertex v. This is not a generic information-theoretic identity: for deterministic algorithms it reduces to H(E(T_v)) ≥ E[|E(T_v)|], i.e., the entropy of the set of hyperedges contained in the triangles output by v must be at least its expected cardinality. For graphs this follows from the specific structure of triangle partitions; for r-uniform hypergraphs, a hyperedge can be shared by many triangles assigned to different vertices, and the graph argument does not obviously survive. The paper gives no proof and no explanation of why the hypergraph case is identical. Moreover, the proof applies the lemma to w = argmax_v |T_v|, a data-dependent vertex, whereas the lemma is stated only for a fixed v. No averaging or symmetrization argument is supplied. If either gap is real, the claimed Ω(n^{r−5/3}/log n) lower bound for CLIQUE and PRIMAL CONGEST is not established, and the main theorem of the paper is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper initiates the study of distributed triangle enumeration in hypergraphs under several new communication models (PC, EC, EB, EU, ES, EP). Its main claims are: (i) an O(n^{r-5/3}/\\log n)-round CLIQUE-model algorithm for triangle enumeration in r-uniform hypergraphs (Theorem 3.1); (ii) a matching Ω(n^{r-5/3}/\\log n) lower bound in CLIQUE and PC (Theorem 3.3), based on a new extremal bound on the number of hyperedges needed to support many triangles (Theorem 3.8); (iii) algorithms for sparse and everywhere-sparse hypergraphs with nearly matching lower bounds (Theorems 4.2, 4.4, 4.14, 4.15); and (iv) a lattice of simulation results among the new models (Propositions 2.2 and 2.3). The upper-bound algorithm is a direct generalization of Dolev–Lenzen–Peled, and the lower-bound strategy follows Izumi–Le Gall. The paper does not actually contain algorithms or theorems for simplex enumeration despite the title and abstract.","tokens_in":32798,"tokens_out":26152,"duration_ms":224763,"significance":"If the main theorems are correct, the paper makes a substantial contribution: it generalizes the optimal triangle-enumeration bounds for CONGEST/CLIQUE from graphs to hypergraphs, introduces a useful family of hypergraph communication models, and provides a novel extremal bound (Theorem 3.8) that may be of independent interest. The sparse-hypergraph results and the maximum-density structural lemma are also valuable and are likely to be reused. The paper is not merely an incremental adaptation: the rank-dependent exponent n^{r-5/3} is a genuine new phenomenon. However, the lower-bound argument is not self-contained, and one of the sparse lower-bound proofs is written in a way that does not support the stated model. These issues must be resolved before the central optimality claims can be accepted.","major_comments":[{"comment":"Lemma 3.20 is load-bearing but is imported from [22] with only the statement that the proof is identical and is not reproduced. This is not acceptable for the central lower bound: the graph proof may not transfer verbatim because in a hypergraph a single hyperedge can participate in many output triangles assigned to different vertices or to the same vertex. The paper must either supply the full proof adapted to hypergraphs or give a precise reference to a statement that covers this setting. Moreover, the lemma is stated for an arbitrary fixed vertex v, but the proof applies it to w = argmax_v |T_v|, a data-dependent vertex. No averaging or symmetrization is provided. As written, the application is unjustified; it can likely be repaired by summing over fixed vertices and using I(E;T) ≥ max_v I(E;T_v), but this needs to be written out.","section":"§3.2, Lemma 3.20 and proof of Theorem 3.3"},{"comment":"The sentence \"Applying Lemma 3.20, we find that I(E;T_w)=Ω(n^{3r-4}) as well\" is not a consequence of the cited lemma. Lemma 3.20 gives I(E;T_w) ≥ E[|E(T_w)|], and Corollary 3.9 only implies E[|E(T_w)|] = Ω(n^{r-2/3}/r^2) when |T_w| = Ω(n^{3r-4}). The quantity |E(T_w)| can be much smaller than |T_w|. The later line also writes \"H(ρ_w)=Ω(n^{r-2/3}/r^2)\" where H(π_w) is clearly intended. These seem to be typographical slips rather than fatal errors, but the entropy chain must be rewritten coherently.","section":"§3.2, proof of Theorem 3.3"},{"comment":"The reduction as written simulates EC rounds with CLIQUE on the subhypergraph H' and concludes a lower bound for EC, not for the stated PC model. In particular, the claim that \"a single round of EC in H' can be simulated by a single round of CLIQUE on H'\" is false: EC permits a pair of vertices to exchange up to deg(u,v) messages per round, and in the constructed dense subhypergraph this can be as large as O(n^{r-2}), whereas CLIQUE permits only one message per pair per round. If the intended reduction was from PC (which is plausible, since PC on H can be simulated by CLIQUE on H' in two rounds), then the text uses \"EC\" where \"PC\" is meant. As written, the proof does not establish Theorem 4.4.","section":"§4.2, proof of Theorem 4.4"},{"comment":"The title and abstract promise \"simplex enumeration\", but the paper contains no simplex enumeration algorithm or theorem; Section 5.1 explicitly lists simplices as future work. The claims in the abstract should be corrected to match the actual contributions (triangle enumeration only), or the missing simplex results must be supplied.","section":"Title and abstract"}],"minor_comments":[{"comment":"The partition is described as \"partition of [n] into n^{2/3} parts of size n^{1/3}\", but the surrounding text and the proof require n^{1/3} parts of size n^{2/3}. This should be corrected.","section":"Algorithm 1, line 3"},{"comment":"The proof cuts off mid-sentence: \"Note that each such triangle is\" — the correctness argument is incomplete and must be finished.","section":"§3.1, proof of Theorem 3.1"},{"comment":"The code contains the literal placeholder \"[TODO: describe the second procedure]\". This must be removed and the missing pseudo-code supplied.","section":"Algorithm 2"},{"comment":"The references to \"Lemma 4.3 in [CITE]\" and \"Lemma 4.2 in [CITE]\" are unresolved placeholders. They should be replaced with the actual lemma numbers from [22] or restated.","section":"§3.2"},{"comment":"Equation (24) has a notation typo: \"E[E(|T_v|)]\" should presumably be \"E[|E(T_v)|]\". Also, in the final paragraph of the proof of Theorem 3.3, \"H(ρ_w)=Ω(n^{r-2/3}/r^2)\" should read \"H(π_w)=...\".","section":"§3.2, Eq. (24) and following lines"},{"comment":"The message-size analysis says O(min{r Δ, n^{r-2}/log n + 1}) but the theorem statement uses Δ2; presumably the first term should be O(r Δ2). Please align the notation.","section":"§3.3, proof of Theorem 3.21"}],"recommendation":"major_revision","confidential_remarks":"The main risk is Lemma 3.20. If the authors can provide a real proof or a precise transfer from the graph case, and correct the EC/PC slip in Theorem 4.4, the paper's central claims are likely salvageable and would be a strong contribution. I do not see grounds to reject on novelty or scope, but the current version is not self-contained enough for the main lower bound, and the sparse lower bound is written for the wrong model in places."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Mike,\n\nThis is a serious but unfinished paper. It extends the graph triangle-enumeration machinery to hypergraphs, introduces a sensible hierarchy of six congestion models, and gives a genuinely new extremal bound (Theorem 3.8) on edges versus triangles in r-uniform hypergraphs. That bound is clean; I checked the multigraph reduction and the Rivin inequality and it holds. The CLIQUE upper bound and the PC/EC upper bounds are mostly adaptations as the authors say, but they are new for hypergraphs, and the density-parameterized algorithms for sparse hypergraphs are a reasonable contribution.\n\nThe main risk is the lower bound. Lemma 3.20—the inequality I(E;T_v) ≥ E[|E(T_v)|]—is imported from Izumi–Le Gall with the comment 'the proof is identical,' and it is then applied to w=argmax_v |T_v|, which is a data-dependent vertex. The lemma as stated is for a fixed v, and the hypergraph version is not obviously identical: an edge can sit in many triangles assigned to different vertices, which breaks the graph-case intuition. If that inequality does not transfer, the Ω(n^{r−5/3}/log n) CLIQUE/PC lower bound is unsupported. This is the load-bearing step and the paper needs to show it, not cite it.\n\nThere are also concrete text problems. The proof of Theorem 3.1 cuts off mid-sentence. Theorem 4.4's reduction says it simulates PC but then describes simulating EC; the claim that vertices in [n′] can simulate the hub and the big edge from their KT_1 initial state is false, so the sparse lower bound is not established as written. Algorithm 2 has a [TODO] in the caption, and the body has unresolved [CITE] placeholders. And the abstract and title promise simplex enumeration that never appears in the paper.\n\nNone of this destroys the framework, and the main triangle results may well be correct. But the paper needs a referee who will force the authors to write out Lemma 3.20 and fix the simulation in Theorem 4.4. I would send it to review—it deserves serious refereeing—but the authors should expect a major-revision report.\n\nRecommended reading for the distributed algorithms group; I would probably cite the model hierarchy and Theorem 3.8 if I work in that area.\n\nBest,","headline":"A useful but unfinished framework for distributed hypergraph triangle enumeration; the main lower bound rests on an imported lemma that is not proved for hypergraphs and the manuscript has multiple broken artifacts.","tokens_in":33321,"tokens_out":15783,"would_cite":true,"duration_ms":134092,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves optimal round bounds—O(n^{r−5/3}/log n)—for distributed triangle enumeration in r-uniform hypergraphs, and gives nearly tight bounds for sparse and everywhere-sparse hypergraphs.","keywords":["hypergraphs","distributed algorithms","triangle enumeration","CLIQUE model","PRIMAL CONGEST","round complexity","extremal hypergraph theory","sparse hypergraphs"],"falsifier":"Compute the mutual information I(E; T_v) for a small 3-uniform hypergraph—for instance, the example in the paper with three edges sharing vertices—and check whether Lemma 3.20's inequality holds: if a vertex's output triangles contain more edges in expectation than the mutual information between the input edge indicators and the output set can account for, the lower bound fails. Separately, in the sparse-hypergraph reduction of Theorem 4.4, count the messages that a single EDGE CLIQUE round can send along parallel edges (up to Δ2 per pair) and check whether the claimed 2-round CLIQUE simulatio","tokens_in":32405,"feed_emoji":"🔺","tokens_out":6453,"duration_ms":54617,"temperature":0.7,"pith_summary":"This paper asks: when a network's communication structure is a hypergraph—where an edge can connect arbitrarily many vertices at once—how many rounds are needed for every triangle in the hypergraph to be output somewhere? It introduces six distributed models that generalize the CONGEST model, then pins down the round complexity of triangle enumeration in the strongest of them. The main result is that in the CLIQUE and PRIMAL CONGEST models, r-uniform hypergraphs can be solved in O(n^{r−5/3}/log n) rounds and no algorithm can do better. The load-bearing step is a new extremal bound on how many triangles a fixed number of hyperedges can support. For sparse and 'everywhere sparse' hypergraphs, the paper gives O(n)-round and O(μ r + log n)-round algorithms, with near-matching lower bounds.","feed_headline":"Optimal bounds for distributed hypergraph triangle listing","feed_subtitle":"Across CLIQUE and PRIMAL CONGEST, r-uniform hypergraphs require Θ(n^{r-5/3}/log n) rounds; sparse cases run in O(n) rounds.","key_machinery":"The load-bearing tool is an extremal bound (Theorem 3.8): an r-uniform hypergraph with m hyperedges can contain at most (√2/3)(m·C(n−3, r−2)·C(r,2))^{3/2} triangles. The proof passes through an induced multigraph—replace each hyperedge by a clique on its vertices, with multiplicity bounded by C(n−2, r−2)—and then applies matrix-trace inequalities to relate triangle count to edge count. This bound drives the lower bound, forcing any vertex that outputs many triangles to have witnessed many hyperedges. The upper bound uses a partition of all possible vertex triples among the n vertices, so that each vertex only needs to learn the characteristic vectors of O(n^{r−2/3}) hyperedges, routed with a","core_discovery":"The central claim is that distributed triangle enumeration in r-uniform hypergraphs has a tight, optimal round complexity in the two most natural models: the CLIQUE model (every pair of vertices can exchange short messages each round) and PRIMAL CONGEST (vertices can exchange messages with any other vertex sharing a hyperedge). The algorithm partitions the n^3 possible vertex triples among the n vertices and routes each vertex the characteristic vectors of incident hyperedges it needs; using a deterministic routing scheme, this runs in O(n^{r−5/3}/log n) rounds. The matching lower bound uses a random r-uniform hypergraph where each hyperedge is present with probability 1/2, shows some vertex","pith_inferences":["If the imported inequality Lemma 3.20 holds, the same information-theoretic framework likely extends to other subgraph enumeration tasks (e.g., clique or simplex listing) in hypergraphs, with extremal edge-support bounds playing the same role.","The EC-model conjecture (an eO(n^{1/3}) round algorithm for bounded-rank hypergraphs) is explicitly left open; the paper's own remarks suggest a suitable generalization of expander-decomposition routing that exploits parallel edges is the natural route.","The sparse lower-bound reduction in Theorem 4.4 appears to omit the up-to-Δ2 parallel-edge messages that a single EDGE CLIQUE round can carry; if that gap is real, the Ω(n^{1−ε}) PRIMAL CONGEST bound for sparse hypergraphs may need a different construction, or may only hold under an additional assumption.","The maximum-density parameter μ and the layered peeling decomposition are natural hypergraph analogues of arboricity; they could become standard parameters for other distributed hypergraph problems such as coloring or independent-set computation."],"forward_implications":["If the bounds are correct, no distributed algorithm can enumerate triangles in r-uniform hypergraphs faster than Ω(n^{r−5/3}/log n) rounds in CLIQUE or PRIMAL CONGEST; the O(n^{r−5/3}/log n) algorithm is therefore optimal.","The lower bound transfers to the EDGE CLIQUE model and the weaker EDGE BROADCAST, EDGE UNICAST, EDGE SOLOCAST, and EDGE PAIRCAST models, giving Ω(n^{1/3}/log n) rounds there, and the model-simulation results make the relative power of the six models precise up to O(r^2) factors.","For sparse hypergraphs, triangle enumeration is solvable in O(n) rounds in EDGE BROADCAST and PRIMAL CONGEST, and any faster PRIMAL CONGEST algorithm is impossible: Ω(n^{1−ε}) rounds are required for every ε > 0.","For hypergraphs with maximum density μ, triangle enumeration runs in O(μ r + log n) rounds without knowing μ in advance, and Ω(μ^{1−ε}) rounds are needed in PRIMAL CONGEST, so the μ-dependence is essentially tight.","The paper's model hierarchy, maximum-density parameter, layered peeling procedure, and graph-reduction techniques provide a template for generalizing other CONGEST algorithms to hypergraphs."],"fun_headline_variants":["Optimal rounds for distributed hypergraph triangle listing","Tight bounds for hypergraph triangle enumeration","Hypergraph triangles: optimal distributed listing","Optimal distributed triangle listing in hypergraphs","Distributed triangle and simplex enumeration: optimal"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire lower bound rests on Lemma 3.20 (Section 3.2), an information-theoretic inequality imported without proof from the graph setting: the set of triangles output by a vertex must carry mutual information at least the expected number of edges contained in those triangles; if that inequality fails for hypergraphs, the Ω(n^{r−5/3}/log n) bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Optimal rounds for distributed hypergraph triangle listing","Tight bounds for hypergraph triangle enumeration","Hypergraph triangles: optimal distributed listing","Optimal distributed triangle listing in hypergraphs","Distributed triangle and simplex enumeration: optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00055,"raw_usage":{"total_tokens":2429,"prompt_tokens":678,"completion_tokens":1751,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":422,"completion_tokens_details":{"reasoning_tokens":1685}},"tokens_in":422,"tokens_out":1751,"duration_ms":12174,"temperature":1.0,"reasoning_tokens":1685,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T22:08:16.691361+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the mutual information I(E; T_v) for a small 3-uniform hypergraph—for instance, the example in the paper with three edges sharing vertices—and check whether Lemma 3.20's inequality holds: if a vertex's output triangles contain more edges in expectation than the mutual information between the input edge indicators and the output set can account for, the lower bound fails. Separately, in the sparse-hypergraph reduction of Theorem 4.4, count the messages that a single EDGE CLIQUE round can send along parallel edges (up to Δ2 per pair) and check whether the claimed 2-round CLIQUE simulatio","supporting_citations":[],"review_version":1}