{"id":"a34ad6cc-b58e-47c8-a3a1-75987315c3df","arxiv_id":"1908.04196","paper_version":4,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A randomized algorithm estimates m(H) within factor (1 +/- epsilon) using O_d(log^{5d+5} n / epsilon^4) GPIS queries for d-uniform hypergraphs, if the sparsification lemma is valid.","lead":"This paper reports a polylogarithmic-query algorithm for estimating the number of hyperedges in a d-uniform hypergraph under a generalized independent-set oracle. It generalizes earlier edge and triangle estimation results, but the central sparsification lemma has a derivation gap that prevents the main theorem from being established as written.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sparsification Lemma 4.1's deviation bound has a log-exponent error: the proof gives sqrt(mo log^{2d-1} n), not sqrt(mo log^d n), so Theorem 1.2's threshold and query complexity do not follow.","rationale":"The reader's weakest assumption points to Lemma 4.1, and the stress-test confirms that the concentration bound in that lemma is the load-bearing step. The proof's own calculations give a deviation with an extra log^{1/2} factor: c_t is proportional to sqrt(|F_o(t)| log^{d-1} n), so sum c_t^2 is proportional to mo log^{2d-2} n, and delta becomes proportional to sqrt(mo log^{2d-1} n). The stated bound sqrt(mo log^d n) is strictly smaller for large n, so the probability tail bound does not follow. This is not a cosmetic typo: the threshold tau in Step 2 is chosen so that the sparsification error is at most epsilon/(4d log n) times the active mass, and with the correct delta the threshold would need an additional polylogarithmic factor, changing the exponent in Theorem 1.2. The additive mo * P(B) term is small, but it cannot compensate for the incorrect delta. The result may still be polylogarithmic with a larger exponent, but the theorem as stated is unsupported. Other flagged issues in Lemmas 6.1 and 6.2 appear more local, so the sparsification gap is the primary reason to reject the current proof.","tokens_in":28200,"tokens_out":21892,"duration_ms":196520,"concrete_test":"Recompute Section 4.2: define c_t = 2^{2d-1} theta^{d-1} sqrt(d! |F_o(t)| log^{d-1} n), form S = sum_t c_t^2 = 2^{4d-2} theta^{2d-2} d! d mo log^{2d-2} n, and compare delta = 2 sqrt(theta log n * S) with the claimed bound 2^{2d} theta^d sqrt(d! mo log^d n) for, say, d = 3 and large log n; the ratio is sqrt(d log n / theta), so the claimed inequality fails for large n.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 4.1 is the central concentration result: it asserts P(|R_d - mo/k| >= 2^{2d} theta^d sqrt(d! mo log^d n)) <= p_d. The inductive proof uses the method of averaged bounded differences with per-vertex bounds c_t = 2^{2d-1} theta^{d-1} sqrt(d! |F_o(t)| log^{d-1} n). Since sum_t |F_o(t)| = d * mo, summing c_t^2 gives S = 2^{4d-2} theta^{2d-2} d! d mo log^{2d-2} n. Setting delta = 2 sqrt(theta log n * S) yields delta = 2^{2d} theta^{d-1/2} sqrt(d! d mo) log^{d-1/2} n, which is larger than the claimed bound 2^{2d} theta^d sqrt(d! mo) log^{d/2} n by a factor sqrt(d log n / theta). The paper's displayed delta instead has log^d n, as if S were proportional to log^{2d-1} n. The additive term mo * P(B), with P(B) <= 2d!/n^{4theta-2d+1} and mo <= n^d, is at most 2d!/n^{4theta-3d+1}; it is not the issue, the delta itself is already too large. Because the threshold tau in Step 2 and the final O_d(log^{5d+5} n / epsilon^4) query bound are derived directly from this lemma, Theorem 1.2 is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a randomized algorithm for estimating the number of hyperedges m(H) in a d-uniform hypergraph on n vertices using queries to a Generalized d-partite Independent Set (GPIS) oracle. The main theorem claims an (1±ε)-approximation with O_d(log^{5d+5} n / ε^4) queries with high probability. The algorithm maintains a data structure of weighted d-partite subhypergraphs; it repeatedly (i) exactly counts subhypergraphs with at most τ ordered hyperedges using a trie-based decision tree, (ii) sparsifies larger subhypergraphs by random vertex coloring together with a random hash on color tuples, and (iii) when too many subhypergraphs accumulate, uses a coarse estimator followed by an importance-sampling step to reduce their number. The central technical ingredient is Lemma 4.1, which asserts that the number of properly colored ordered hyperedges R_d satisfies |R_d − m_o/k| ≤ 2^{2d} θ^d sqrt(d! m_o log^d n) with probability at least 1 − d!/n^{4θ−2d}. The proof of this lemma is by induction on d using the method of averaged bounded differences. The paper also proves that the GPIS1 and GPIS2 oracle variants can be simulated by polylogarithmically many GPIS queries.","tokens_in":28539,"tokens_out":25930,"duration_ms":242261,"significance":"If correct, the main result would be the first polylogarithmic-query algorithm for d-uniform hyperedge estimation without the parameter Δ that appeared in the triangle-estimation work of Bhattacharya et al., and it would generalize the edge-estimation result of Beame et al. The paper is clearly written and the supporting lemmas (exact estimation, coarse estimation, importance sampling) are presented in detail. The comparison with the concurrent work of Dell et al. is transparent and helpful. However, the central sparsification lemma has a substantive proof gap: the calculation of the concentration parameter δ gives a deviation of order sqrt(m_o) log^{d−1/2} n rather than sqrt(m_o) log^{d/2} n, and the application of the averaged-bounded-differences inequality is not justified because the required bounds are not established on the conditional space. These issues are load-bearing for the threshold setting and for the final query bound. As a result, the main theorem is not established in the present manuscript.","major_comments":[{"comment":"The computation of δ is incorrect. With c_t = 2^{2d−1} θ^{d−1} sqrt(d! F_o(t) log^{d−1} n) and ∑_t F_o(t) = d m_o(A), one obtains ∑_t c_t^2 = 2^{4d−2} θ^{2d−2} d! d m_o(A) log^{2d−2} n. Therefore δ = 2 sqrt(θ log n · ∑_t c_t^2) = 2^{2d} θ^{d−1/2} sqrt(d! d m_o(A)) log^{d−1/2} n, not the paper's 2^{2d} θ^{d−1/2} sqrt(d! m_o(A) log^d n). For d ≥ 2, the correct δ exceeds the bound asserted in Lemma 4.1 by a factor θ^{−1/2} sqrt(d) log^{(d−1)/2} n, and the additive m_o(A)P(B) term in the next display cannot close this gap. Since the threshold τ in Section 7 and Equation (3) in Section 8 are derived from the claimed log^{d/2} bound, Theorem 1.2 is not supported as written.","section":"Section 4.2, proof of Lemma 4.1"},{"comment":"The application of the averaged bounded differences inequality is not justified. Lemma A.2 requires, for the event B, a bound on the conditional expectations given B^c, namely |E[f | X_1,...,X_{i−1}, X_i=a_i, B^c] − E[f | ..., X_i=a'_i, B^c]| ≤ c_i. The proof, however, bounds the unconditional differences E_t R_d via Claim 4.4. Conditioning on B^c — the event that all these differences are small — changes the distribution of the remaining colors and can alter the conditional differences. No argument is given that the c_t bounds hold on the conditional space B^c, so the concentration step in the proof of Lemma 4.1 is not established.","section":"Section 4.2 and Lemma A.2"},{"comment":"Observation 8.4 is stated only for the case that the data structure contains exactly one tuple after iteration i, but its proof immediately treats the case of r > N tuples (Step 4), and Lemma 8.2 applies the observation to all iterations, during which D generally contains many tuples. As stated, the observation does not support the chain of (1±λ)-approximations used in the proof of Lemma 8.2; the statement and proof need to be generalized to arbitrary tuple sets.","section":"Section 8, Observation 8.4 and proof of Lemma 8.2"}],"minor_comments":[{"comment":"The condition 'while there is a leaf node mo(B_1^{[b_1]},...,B_t^{[b_t]}) = 0 in the tree with label 1' should read 'with label 1'; the equality to 0 is inconsistent with the surrounding text and with the prose description of the algorithm.","section":"Algorithm 1, line 5"},{"comment":"The displayed inequalities for P(E1) and P(E_i | ...) bound the probabilities of the complementary events; as printed they have the wrong sign. The final line P(∩ E_i) ≥ (1−e^{−1})^d reveals the intended meaning, but the inequalities need to be corrected.","section":"Lemma 6.2, proof"},{"comment":"The inequality 'P(B) ≤ 2d!/n^{4θ−4d+1}' appears to be a typo for 2d!/n^{4θ−2d+1}, which is the value used in the next display and follows from the union bound over t.","section":"Section 4.2"},{"comment":"The sentence 'Since the algorithm of Lemma 3.4 does not require any queries, the number of GPIS2 queries in this step in each iteration is O_d(log^{d+1} n) per tuple' is confusing: the O_d(log^{d+1} n) bound comes from the coarse-estimation step, not from Lemma 3.4 itself.","section":"Section 7, Step 4"},{"comment":"In the definition of the events E_i, the line 'Aj((Q_{j−1},U_{j−1}),q_j)∩B_{j,q}≠∅, where 2≤i≤d−1' uses j in place of i and should be rephrased for clarity.","section":"Lemma 6.2, definitions of events"}],"recommendation":"reject","confidential_remarks":"The main result may be salvageable in some form, but the submitted proof of the central sparsification lemma is not valid. The error in the δ calculation is an algebraic issue, but the conditional-bounded-differences gap is more fundamental and would require a substantially different concentration argument. I would not exclude the possibility that the approach can be repaired, but the manuscript as it stands does not establish its central claim. The paper also acknowledges significant overlap with the concurrent work of Dell et al.; the novelty claim rests entirely on the sparsification lemma, and that lemma is the part whose proof is not sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nShort version: the central objection in the report is, as far as I can tell, wrong. The claimed log-exponent gap in Lemma 4.1 comes from pulling log^{d-1} out of the square root. The proof's c_t is c_t = const * sqrt(d! |F_o(t)| log^{d-1} n), so after squaring you get |F_o(t)| log^{d-1} n, and after summing over t with sum |F_o(t)| = d mo, delta becomes const * sqrt(mo log^d n) = const sqrt(mo) log^{d/2} n, which is exactly the lemma's bound. The stress-test note squares as if the log were outside the sqrt; it's an algebra slip, not a gap in the paper.\n\nThat matters because the rest of the architecture hangs on Lemma 4.1, and the lemma looks fine. The sparsification idea is genuinely the new thing: a d-dimensional hash with P=1/k per tuple, used to induct on d, which removes the Delta-dependence from the earlier triangle work. The extension to d-uniform hypergraphs and the polylog query bound are real. The acknowledgment of the concurrent Dell et al. result is honest.\n\nThere are minor blemishes. Lemma 6.2's proof has a direction slip: it writes P(E1) ≤ exp(-1) where it means P(E1^c) ≤ exp(-1); the conclusion still holds because it later uses (1 - e^{-1})^d. A few displayed equations have small notation typos. None of these affect the main theorem.\n\nSo my recommendation: send it to a serious referee. The result is significant enough, the central lemma survives the attack in the stress test, and the writing, while dense, is at a standard where a careful referee can check the steps. The report's REJECT should not be acted on as-is.","headline":"The reported log-exponent flaw in Lemma 4.1 doesn't survive contact with the equation; the c_t bound already puts log^{d-1} inside the square root, so delta comes out with log^{d/2}. The paper's central claim looks sound and deserves real review.","tokens_in":29119,"tokens_out":10582,"would_cite":true,"duration_ms":93953,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","68Q25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every fixed d, the number of hyperedges in a d-uniform hypergraph can be estimated within a (1±epsilon) factor using only polylogarithmically many GPIS queries, with no dependence on hyperedge intersection multiplicity.","keywords":["hypergraph estimation","GPIS oracle","subset queries","randomized algorithms","sparsification","query complexity","d-uniform hypergraphs","polylogarithmic query complexity"],"falsifier":"Recompute the averaged-bounded-differences step in the proof of Lemma 4.1. Since c_t = $2^{{2d-1}}$ $theta^{{d-1}}$ $\\sqrt$(d! |F_o(t)| $log^{{d-1}}$ n), the sum over t of $c_t^{2}$ is of order m_0(A) $log^{{2d-1}}$ n, not m_0(A) log^d n. Setting delta = $\\sqrt$(sum_t $c_t^{2}$) therefore gives a deviation of order $\\sqrt$(m_0(A)) $log^{{d-1/2}}$ n, while the printed lemma's bound is $\\sqrt$(m_0(A)) $log^{{d/2}}$ n. Checking this calculation either confirms the printed bound or shows that the sparsification guarantee, and hence the theorem's query count, needs a larger log exponent.","tokens_in":27942,"feed_emoji":"🧮","tokens_out":6912,"duration_ms":66691,"temperature":0.7,"pith_summary":"The paper tries to establish that, for any fixed uniformity d, the number of hyperedges in a d-uniform hypergraph can be approximated to within a (1±epsilon) factor using only O_d($log^{{5d+5}}$ n / $epsilon^{4}$) yes/no queries to a Generalized d-partite Independent Set (GPIS) oracle, with high probability. This would extend edge and triangle estimation to hypergraphs while removing the earlier need to bound how many hyperedges can share an edge. It would mean that even with complicated intersection patterns, a randomized coloring can sparsify the hypergraph into manageable pieces while approximately preserving the total count. The proof's engine is a sparsification lemma asserting concentration of the number of properly colored ordered hyperedges around its mean.","feed_headline":"Polylog queries estimate hyperedge counts in d-uniform hypergraphs","feed_subtitle":"Random coloring sparsifies dense hypergraphs, cutting the query cost from polynomial to polylogarithmic.","key_machinery":"The load-bearing object is the sparsification lemma (Lemma 4.1). It colors the vertices of a d-uniform hypergraph with k colors and uses an independent hash bit h_d(c_1,...,c_d) for each d-tuple of colors, defining a properly colored ordered hyperedge as one whose vertex colors form a tuple with hash value 1. The count R_d of properly colored ordered hyperedges has expectation mo($A_1^{{[a_1]}}$,...,$A_s^{{[a_s]}}$)/k, and the lemma claims a concentration bound of order $\\sqrt$(m log^d n) with high probability. This is what lets the algorithm replace a dense d-partite subhypergraph by roughly k independent sparse pieces, each of whose counts can be handled exactly or coarsely; the d-fold recursion in the proof of the lemma is what removes the earlier dependence on the maximum number of hyperedges sharing an edge.","core_discovery":"The central claim is Theorem 1.2: for any epsilon in (0,1), Hyperedge-Estimation can be solved using O_d($log^{{5d+5}}$ n / $epsilon^{4}$) GPIS queries with high probability, where the hidden constant depends only on d. The underlying discovery is a sparsification routine for arbitrary d-uniform hypergraphs. Vertices are colored uniformly at random with k colors, and a hash function h_d on d-tuples of colors independently decides which color combinations count as proper; the number R_d of properly colored ordered hyperedges has expectation m/k. The paper argues that R_d concentrates near m/k, so scaling by k gives a good estimate, and the argument recurses on d by fixing one vertex at a time. Around this sparsification step, the algorithm alternates exact counting for sparse subhypergraphs, coarse estimation via sampled verification, and importance sampling to keep the number of subhypergraphs bounded, yielding the polylogarithmic query bound.","pith_inferences":["The same color-tuple hashing idea may apply to counting copies of fixed small subhypergraphs, not only all d-uniform hyperedges, by choosing the hash domain to match the pattern being counted.","One could try to derandomize the coloring with small sample spaces, which would turn the high-probability query algorithm into a deterministic one.","Identifying the exact dependence on d would clarify whether the polylogarithmic exponent is close to optimal for this oracle model."],"forward_implications":["For any fixed d, hyperedge counts become accessible with only polylogarithmically many GPIS queries, independent of the number of hyperedges or their intersection multiplicities.","The result generalizes edge and triangle estimation to d-uniform hypergraphs, providing a single query framework for all d.","The sparsification routine itself is a reusable tool for turning dense uniform hypergraphs into sparse pieces while preserving approximate counts.","The algorithm's query complexity is O_d(log^{5d+5} n / epsilon^4), so for constant d it remains polylogarithmic in n and polynomial in 1/epsilon."],"supporting_citations":[{"why":"Supplies the sparsification-by-random-coloring approach and the importance-sampling lemma (Lemma A.6) that the algorithm builds on.","marker":"[BHR+18]"},{"why":"Prior triangle-estimation result that this paper generalizes; its dependence on the maximum number of triangles sharing an edge motivates the new hashing scheme.","marker":"[BBGM19]"},{"why":"Concurrent independent result for hyperedge estimation with colorful independent set queries, used as a comparison for query complexity.","marker":"[DLM19]"},{"why":"Provides the method of averaged bounded differences and the Hoeffding and Chernoff bounds used in the sparsification proof.","marker":"[DP09]"},{"why":"Introduces the GPIS oracle definition used throughout the paper.","marker":"[BGK+18a]"},{"why":"Formalizes the subset query model that GPIS generalizes.","marker":"[RT16]"}],"fun_headline_variants":["Polylog queries count hyperedges in d-uniform hypergraphs","Sparsification of d-uniform hypergraphs enables polylog query estimation","Generalized independent set oracle yields polylog hyperedge estimation","Hyperedge estimation with polylogarithmic GPIS queries","Random coloring cuts hyperedge query cost to polylog"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire query bound rests on the sparsification lemma's concentration inequality, which states that the number of properly colored hyperedges stays within roughly $\\sqrt$(m log^d n) of its expectation; if the true deviation is larger, the thresholds and final query count do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Polylog queries count hyperedges in d-uniform hypergraphs","Sparsification of d-uniform hypergraphs enables polylog query estimation","Generalized independent set oracle yields polylog hyperedge estimation","Hyperedge estimation with polylogarithmic GPIS queries","Random coloring cuts hyperedge query cost to polylog"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00026,"raw_usage":{"total_tokens":1661,"prompt_tokens":1089,"completion_tokens":572,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":705,"completion_tokens_details":{"reasoning_tokens":484}},"tokens_in":705,"tokens_out":572,"duration_ms":6502,"temperature":1.0,"reasoning_tokens":484,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:50:39.225617+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the averaged-bounded-differences step in the proof of Lemma 4.1. Since c_t = $2^{{2d-1}}$ $theta^{{d-1}}$ $\\sqrt$(d! |F_o(t)| $log^{{d-1}}$ n), the sum over t of $c_t^{2}$ is of order m_0(A) $log^{{2d-1}}$ n, not m_0(A) log^d n. Setting delta = $\\sqrt$(sum_t $c_t^{2}$) therefore gives a deviation of order $\\sqrt$(m_0(A)) $log^{{d-1/2}}$ n, while the printed lemma's bound is $\\sqrt$(m_0(A)) $log^{{d/2}}$ n. Checking this calculation either confirms the printed bound or shows that the sparsification guarantee, and hence the theorem's query count, needs a larger log exponent.","supporting_citations":[],"review_version":1}