{"id":"bbc95e66-cf4b-4c67-a5d7-ad0ff2371cea","arxiv_id":"2412.21155","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A unified tensor-based lower bound shows low-coordinate-degree tests fail for generalized stochastic block models at the generalized Kesten-Stigum threshold.","lead":"This paper proves that many simple statistics, functions that look at only a few coordinates at a time, cannot detect hidden community structure in random networks unless the signal is strong enough. It gives one unified mathematical framework for several detection problems and strengthens known limits for group synchronization.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"HSBM application proof in §4.3.2 contains a prefactor error in the computation of T^(2); as printed, the calculation does not yield Theorem 1.19.","rationale":"The reader's verdict is CONDITIONAL, and I agree with conditionality: the abstract machinery in Sections 3.1-3.3 is coherent, the graph SBM and group synchronization applications have correct norm computations, and the multi-frequency synchronization application is consistent. My stress-test does not change the verdict. However, I do not think the single most load-bearing issue is the weak-symmetry assumption, which is a clearly stated hypothesis and is verified for the applications; rather, it is the concrete prefactor error in the hypergraph SBM proof. That error is load-bearing because Theorem 1.19 is one of the headline applications and is not implied by the displayed computation as written. The error appears to be fixable: correcting the prefactor to k^{3-p}/lambda recovers exactly the generalized Kesten-Stigum threshold stated in (7), and the higher-order injective norm condition of Theorem 1.14 should also hold for HSBMs, but it is not shown. This is an exposition and correctness gap in an application proof, not an invalidation of the central general theorems. I therefore recommend keeping the reader's CONDITIONAL verdict rather than upgrading or downgrading it.","tokens_in":33238,"tokens_out":19513,"duration_ms":197827,"concrete_test":"Independently recompute T^(2) for the hypergraph SBM from Definition 1.9, specializing to the symmetric two-community case with k=2, p=3, and compare the prefactor with the formula derived in Section 4.3.1. If the recomputed prefactor is (a-b)^2 / (3*(a+3b)*n^2) rather than (a+3b)*(a-b)^2 / (3*n^2), then the printed Section 4.3.2 algebra is incorrect and Theorem 1.19 needs a corrected proof; the same recomputation should also confirm the bound ||T^(j)||_{inj} <= C/n^{p-1} for every 3 <= j <= p.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1.19 (oddly headed 'Proof of Theorem 1.16') computes the marginalized characteristic tensor T^(2) for a general hypergraph SBM and obtains a prefactor of order k^{p-3} * lambda * max_j |lambda_j|^2 / n^{p-1}. Recomputing from Definition 1.9 and Proposition 4.2 gives instead a prefactor proportional to k^{3-p} * max_j |lambda_j|^2 / (lambda * n^{p-1}). The discrepancy is visible already in the symmetric two-community case with k=2, p=3: the printed formula would give ||T^(2)|| ~ lambda*(alpha-beta)^2 / (3 n^2), while the warmup computation in Section 4.3.1 gives (alpha-beta)^2 / (3*lambda*n^2), and these differ by a factor of lambda^2 = (alpha+3*beta)^2. With the corrected prefactor, Theorem 1.14 indeed yields the stated Kesten-Stigum threshold in (7), so the theorem may be salvageable; but as written, the displayed algebra in Section 4.3.2 does not support the application. Additionally, Theorem 1.14 requires ||T^(j)||_{inj} <= C / n^{p-1} for all 3 <= j <= p, and Section 4.3.2 verifies only the j=2 case; this second condition also needs to be checked for hypergraph SBMs.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a unified theory of low coordinate degree function (LCDF) lower bounds for categorical signal detection, centered on generalized stochastic block models (GSBMs). The key object is the characteristic tensor T of a GSBM; the marginal order p* — the smallest order of a nonvanishing marginal characteristic tensor — is shown to determine the detection threshold in analogy with the order of a spiked tensor. Theorem 1.13 gives a general lower bound on the coordinate advantage under injective-norm conditions and D(n) ≤ cn; Theorem 1.14 specializes to marginal order 2, with the sharp constant k²/(p(p−1)n^{p−1}) and degree D(n) = O(n/log n). Applications are given to graph SBMs (Theorem 1.16, threshold max_j |λ_j|² < kλ), regular hypergraph SBMs (Theorem 1.19, generalized Kesten–Stigum threshold (7)), truth-or-Haar group synchronization and abelian group sumset models (Theorems 1.22 and 1.24, γ < 1), and random XOR-SAT as a higher-marginal-order example; the technical results are also used to improve the multi-frequency group synchronization degree bound from o(n^{1/3}) to Ω(n) (Theorem 4.5). The technical infrastructure includes a sharp vector Bernstein inequality (Lemma 2.1), subgaussian tail and moment bounds for Pearson's chi-square statistic (Lemma 2.4, Corollary 2.6), and a general truncation lemma for truncated exponentials (Lemma 2.10).","tokens_in":33480,"tokens_out":53161,"duration_ms":450438,"significance":"If the issues raised below are repaired, this is a substantial contribution to the low-degree testing literature. The marginal-order framework gives a genuinely general reduction: the hard content of a GSBM testing problem is compressed into finitely many tensors, and the resulting lower bounds match the known generalized Kesten–Stigum thresholds in the graph, regular hypergraph, and synchronization applications. The paper is commendably free of fitted parameters: the constants in Theorems 1.13 and 1.14 are explicit, the proofs are self-contained except for the cited companion theorems, and the sharp-factor claims are testable. The technical core is reusable beyond this paper: Lemma 2.1 avoids the Trace(Cov) loss of standard vector Bernstein arguments; Corollary 2.6 gives the right chi-square_Pear moment scaling for degree up to linear in n; and Lemma 2.10 is a clean formalization of the 'race' between degree growth and overlap fluctuations. The Ω(n)-degree lower bound for multi-frequency synchronization is a concrete quantitative advance over the n^{1/3} bound of [KBK24].","major_comments":[{"comment":"The tail-bound step immediately after Eq. (12) claims that 'provided that we take C even larger and restrict to t ≤ n/C, we may ensure that all of the terms in the latter sum are at most the first probability'. This is not correct as stated. For j = 3 and t = n/C, the j-th event threshold (1/C) n^{1−2/j} t^{2/j} equals n·C^{−5/3}, whereas the first event threshold 2t(1−ε/2)/(1−ε) is Θ(n/C); their ratio is Θ(C^{−2/3}), which vanishes as C grows, so the j-th event has strictly larger probability than the first, and increasing C (which loosens the bounds in (12)) only increases the discrepancy. The gap is repairable: one can bound each P[Rn,j ≥ εt/(2p)] directly via Lemma 2.4 and choose A(n) = n/C₀ with C₀ depending on the theorem's constant C, since t^{2/j−1} is decreasing in t, so a_j/t ≥ c_j C₀^{1−2/j} holds uniformly over t ≤ n/C₀. Thus the statement of Theorem 1.14 appears correct, but the printed proof of the paper's central theorem contains a genuine gap that must be fixed.","section":"§3.3, proof of Theorem 1.14"},{"comment":"The displayed marginalization of the characteristic tensor is incorrect. From Proposition 4.2 and Definition 1.9 (whose contraction normalization is k^{−2(p−2)}, not k^{2(p−2)}), one obtains T^{(p)} ≈ (k^{p−1}/(p! λ N))(Q − (λ/k^{p−1})1^{⊗p})^{⊗2} with N = binom(n,p−1), and contracting p−2 index pairs with the all-ones vector gives T^{(2)} ≈ (k^{3−p}/(p! λ N))(Q[1,...,1,·,·] − (λ/k)1^{⊗2})^{⊗2}, hence ‖T^{(2)}‖ ≈ k^{3−p} max_j |λ_j(Q[1,...,1,·,·])|² / (p λ n^{p−1}). The printed value k^{p−3} λ max_j |λ_j|²/(p n^{p−1}) differs by a factor k^{2(p−3)}λ²; for the symmetric two-community case k = 2, p = 3 it gives λ²(α−β)²/(3n²) instead of the warm-up value (α−β)²/(3λn²) from §4.3.1 (with λ = α + 3β). Consequently, the algebra as printed does not yield the theorem's condition (7) — it would instead imply max_j |λ_j|² < k^{5−p}/((p−1)λ) — whereas the corrected value yields exactly (7). This is a load-bearing error in the HSBM application and must be corrected.","section":"§4.3.2, proof of Theorem 1.19"},{"comment":"Theorem 1.14 requires ‖T^{(j)}_n‖_{inj} ≤ C/n^{p−1} for every 3 ≤ j ≤ p, but the proof verifies only the j = 2 condition. For the HSBM this verification is routine — T^{(j)} is, up to the prefactor (p! q N k^{2(p−j)})^{−1} with q = λ/k^{p−1}, the flattened square of the fixed tensor Q[1^{p−j},·^j] − (λ/k^{j−1})1^{⊗j}, whose entries are bounded by constants depending only on p and k — but the check must appear in the proof for the application of Theorem 1.14 to be complete.","section":"§4.3.2, proof of Theorem 1.19"}],"minor_comments":[{"comment":"The proof of Theorem 1.19 is headed 'Proof of Theorem 1.16'; the heading should be corrected.","section":"§4.3.2"},{"comment":"The domain of x^{(1)}, x^{(2)} is written as Unif([k]^p) in three places; since the overlap is defined on label vectors of length n, these should read Unif([k]^n).","section":"§3.1, proof of Lemma 3.3"},{"comment":"The statement contains the typo 'for constant s C > 0'.","section":"Theorem 1.14 statement"},{"comment":"Theorems 1.26 and 1.28 are stated without proof; since the author describes the calculations as trivial, the journal version should include them so that the paper is self-contained.","section":"§1.4.4"},{"comment":"Lemma 3.3 invokes [Kun24, Theorem 3.5] as a black box, and the proof of Theorem 4.5 similarly uses Eq. (6.4) of [KBK24] without statement; since [Kun24] is an unpublished companion preprint, the precise hypotheses of the invoked theorem (and the cited equation) should be restated so the present arguments can be checked independently.","section":"§3.1 and §4.4.3"},{"comment":"The corollary states the advantage bound without the square that appears in Lemma 3.3; the weaker bound is valid because the argument of exp≤D is nonnegative and exp≤D ≥ 1, but the two statements should be aligned to avoid confusion.","section":"Corollary 3.5"},{"comment":"The improvement is asserted for general finite groups and the circle group U(1), but only the cyclic case is treated; a sentence explaining the reduction would help.","section":"§4.4.3"}],"recommendation":"major_revision","confidential_remarks":"The paper depends heavily on the companion preprint [Kun24] and on [KBK24]; the editor may wish to confirm availability of both before final acceptance. The two places the author must fix are the tail bound in the proof of Theorem 1.14 (§3.3) and the prefactor computation in §4.3.2. I independently recomputed the HSBM marginalization and the stated Kesten–Stigum threshold (7) is correct; the errors are in the printed algebra, not in the theorem statements, and both are repairable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core of this paper is a genuinely new and elegant framework: a unified LCDF lower-bound technology for categorical GSBMs, governed by marginal characteristic tensors and marginal order. The applications to general graph SBMs, p>=3 hypergraph SBMs, abelian sumset, and Gaussian multi-frequency synchronization are new and match known Kesten-Stigum thresholds. The Pearson chi-square moment and tail bounds in Section 2 are themselves a useful technical contribution, and the multi-frequency degree improvement to O(n) is notable. The abstract results in Sections 3.1-3.3 are coherent; the use of [Kun24, Thm 3.5] as a black box is acceptable since it is prior independent work.\n\nThe main soft spot is real and lands exactly where the stress-test says. In Section 4.3.2, the displayed prefactor for T^(2) is k^{p-3} * lambda, but recomputing from Definition 1.9 and Proposition 4.2 gives k^{3-p} / lambda (up to constants depending only on p). The warmup computation in 4.3.1 confirms the corrected version. The good news: with the corrected prefactor, Theorem 1.14 delivers the stated KS threshold in (7), so the theorem is salvageable. But as printed, the algebra does not support the application. Also, Theorem 1.14 requires bounds on ||T^(j)||_inj for all 3 <= j <= p, while 4.3.2 only checks j=2; this is a gap that needs to be filled, though it looks minor given the rough bounding available. The heading \"Proof of Theorem 1.16\" in 4.3.2 is a typo for Theorem 1.19.\n\nI don't see a load-bearing flaw in the central machinery or the other applications. The graph SBM and group synchronization calculations check out. The paper is honest about the weak-symmetry assumption and about what it does not cover. This is a serious theory paper that should go to peer review; the referee will need to ask for a corrected HSBM computation and an explicit check of the higher marginal tensors, but the main results are likely sound after those fixes. I would cite this work and would bring it to a theory reading group.","headline":"Strong novel framework for LCDF lower bounds in categorical GSBMs, but the hypergraph SBM proof has a fixable prefactor error that must be corrected.","tokens_in":34085,"tokens_out":5399,"would_cite":true,"duration_ms":50260,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F03","62H30","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Low-coordinate-degree functions cannot strongly separate categorical signals below generalized Kesten-Stigum thresholds.","keywords":["low coordinate degree functions","generalized stochastic block model","Kesten-Stigum threshold","hypothesis testing lower bounds","group synchronization","characteristic tensor","marginal order","statistical-computational gaps"],"falsifier":"Compute the coordinate advantage for the two-community symmetric SBM with $(\\alpha-\\beta)^2/(2(\\alpha+\\beta))=0.99$ and degree $D(n)=n/\\log n$; the theorem predicts the advantage stays $O(1)$, so observing it diverge would refute the sharp constant in Theorem 1.14.","tokens_in":32951,"feed_emoji":"🧩","tokens_out":7986,"duration_ms":75869,"temperature":0.7,"pith_summary":"This paper asks when algorithms built from low-coordinate-degree functions, meaning linear combinations of functions that read only a few entries of the observation, can detect categorical structure in high-dimensional data such as hidden community labels or group assignments. It establishes that for a broad class of generalized stochastic block models, the entire difficulty of detection is captured by a finite tensor called the characteristic tensor and its marginalizations. The main theorems give conditions on the norms of these tensors under which no low-coordinate-degree test can strongly separate the planted from the unplanted distribution; applied to graph and hypergraph SBMs, these conditions match generalized Kesten-Stigum thresholds, and applied to group synchronization and abelian sumset problems they give degree-O(n/log n) barriers. Because low-coordinate-degree functions include low-degree polynomials, these are lower bounds against a larger class than usual low-degree algorithms.","feed_headline":"Low-coordinate tests fail below Kesten-Stigum thresholds","feed_subtitle":"New lower bounds cover graph and hypergraph SBMs, group synchronization, and sumset models in a single tensor framework.","key_machinery":"The characteristic tensor $T$ has entries given by expected products of centered likelihood ratios of the channel measures, and the marginal order is the smallest order at which a marginalized characteristic tensor is nonzero. The key identity is the overlap expansion $\\langle T,z^{\\otimes p}\\rangle=\\sum_{j=p_*}^{p} \\binom{p}{j} n^{p-j}\\langle T^{(j)},\\bar{z}^{\\otimes j}\\rangle$, where $z$ is a multinomial count of label pairs in two independent draws of hidden labels; this reduces the coordinate advantage to a truncated exponential of a Pearson chi-square statistic. The proof then controls the advantage through a sharp vector Bernstein inequality and moment/tail bounds for Pearson's chi-square, together with a local-Chernoff-type lemma for truncated exponentials.","core_discovery":"The central claim is that a generalized stochastic block model of marginal order $p_*$ behaves, for low-coordinate-degree testing, like a spiked $p_*$-tensor model: the maximal advantage of any coordinate-degree-$D$ function is bounded by the expectation of a truncated exponential of a random overlap, and this overlap is a polynomial in a multinomial count vector whose coefficients are the marginalized characteristic tensors. For $p_*=2$ the paper proves a sharp lower bound with the precise constant $k^2/(p(p-1))$ in the operator-norm condition, valid for $D(n)=O(n/\\log n)$; for $p_*\\ge 3$ it proves a degree-signal tradeoff valid for $D(n)\\le c n$. The applications show that in nearly arbitrary graph and regular hypergraph SBMs the generalized Kesten-Stigum threshold is exactly where low-coordinate-degree tests lose all power, and that truth-or-Haar synchronization and abelian sumset models are hard for coordinate degree $O(n/\\log n)$ whenever the signal parameter $\\gamma<1$.","pith_inferences":["Extending the paper's spiked-tensor analogy, the same degree-versus-signal tradeoff should appear in statistical query and sum-of-squares algorithms for GSBMs, but the paper does not prove this for those classes.","A testable extension is to compute the marginal order of sumset models over non-abelian groups; if weak symmetry is the only obstruction, a more problem-specific overlap calculation might recover the identical O(n/\\log n) barrier.","The linear-degree improvement for multi-frequency synchronization likely extends to other group synchronization noise models whose analyses reduce to Pearson chi-square moments, since the moment bound is the only model-specific input."],"forward_implications":["For graph SBMs, no function of coordinate degree O(n/\\log n) can strongly separate planted from null below the generalized Kesten-Stigum threshold $\\max_j |\\lambda_j(Q)|^2 < k\\lambda_1(Q)$.","For regular hypergraph SBMs, the same barrier holds under a generalized threshold involving the top eigenvector of the marginalized interaction tensor, giving new evidence for statistical-to-computational gaps.","For truth-or-Haar group synchronization over any finite group, and truth-or-Haar sumset over any finite abelian group, coordinate degree O(n/\\log n) cannot test when $\\gamma<1$.","For Gaussian multi-frequency synchronization, the polynomial-degree barrier improves from o(n^{1/3}) to a linear constant times n, for any $\\lambda<1$.","For models with marginal order $p_*\\ge 3$, the lower bound gives a smooth tradeoff: larger coordinate degree, and hence more runtime, permits detection at smaller signal strength, matching the spiked-tensor analogy."],"supporting_citations":[{"why":"It supplies the low-coordinate-degree overlap framework and the bound on the coordinate advantage used as the starting point here.","marker":"[Kun24]"},{"why":"It provides the low-degree advantage formalism and the spiked-matrix/spiked-tensor comparison underlying the sharp thresholds.","marker":"[KWB22]"},{"why":"It gives the prior lower bound for the symmetric two-community SBM that Theorem 1.16 generalizes to arbitrary interaction matrices.","marker":"[BBK+21]"},{"why":"It gives the o(n^{1/3}) multi-frequency synchronization bound that Theorem 4.5 improves to a linear degree via new chi-square moment control.","marker":"[KBK24]"},{"why":"It predicts the gamma-less-than-1 computational threshold for group synchronization and supplies algorithmic context.","marker":"[PWBM16]"},{"why":"It defines the generalized SBM family whose spectral analysis this paper recovers as testing lower bounds.","marker":"[XML14]"},{"why":"It establishes the Kesten-Stigum threshold for stochastic block models that the lower bounds match.","marker":"[DKMZ11a]"},{"why":"It provides the Kikuchi-spectral algorithm for planted XOR-SAT whose runtime scaling the higher-marginal-order lower bound complements.","marker":"[WEM19]"}],"fun_headline_variants":["Low-coordinate tests hit Kesten-Stigum wall across SBM families","Tensor analogy pins down SBM hardness for low-coordinate tests","For SBMs, low-degree tests fail exactly at Kesten-Stigum threshold","Low-coordinate limits match Kesten-Stigum in graphs and hypergraphs","Categorical signals: low-coordinate tests lose at generalized KS"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument depends on the model being weakly symmetric: permuting the p labels in any pair of channel measures must leave the centered likelihood-ratio inner product unchanged, so that the overlap collapses into a symmetric tensor contraction.","fun_headline_variants_meta":{"raw":{"variants":["Low-coordinate tests hit Kesten-Stigum wall across SBM families","Tensor analogy pins down SBM hardness for low-coordinate tests","For SBMs, low-degree tests fail exactly at Kesten-Stigum threshold","Low-coordinate limits match Kesten-Stigum in graphs and hypergraphs","Categorical signals: low-coordinate tests lose at generalized KS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000232,"raw_usage":{"total_tokens":1566,"prompt_tokens":1095,"completion_tokens":471,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":711,"completion_tokens_details":{"reasoning_tokens":375}},"tokens_in":711,"tokens_out":471,"duration_ms":4648,"temperature":1.0,"reasoning_tokens":375,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:02:16.970791+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the coordinate advantage for the two-community symmetric SBM with $(\\alpha-\\beta)^2/(2(\\alpha+\\beta))=0.99$ and degree $D(n)=n/\\log n$; the theorem predicts the advantage stays $O(1)$, so observing it diverge would refute the sharp constant in Theorem 1.14.","supporting_citations":[],"review_version":1}