REVIEW 3 major objections 7 minor 1 cited by
Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
T0 review · 3 major / 7 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Low-coordinate-degree functions cannot strongly separate categorical signals below generalized Kesten-Stigum thresholds.
desk verdict Strong novel framework for LCDF lower bounds in categorical GSBMs, but the hypergraph SBM proof has a fixable prefactor error that must be corrected. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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$.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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 (3)
- [§3.3, proof of Theorem 1.14] 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.
- [§4.3.2, proof of Theorem 1.19] 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.
- [§4.3.2, proof of Theorem 1.19] 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.
minor comments (7)
- [§4.3.2] The proof of Theorem 1.19 is headed 'Proof of Theorem 1.16'; the heading should be corrected.
- [§3.1, proof of Lemma 3.3] 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).
- [Theorem 1.14 statement] The statement contains the typo 'for constant s C > 0'.
- [§1.4.4] 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.
- [§3.1 and §4.4.3] 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.
- [Corollary 3.5] 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.
- [§4.4.3] 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.
Circularity Check
No significant circularity; the bounds are derived from characteristic-tensor computations and a prior general overlap theorem, not fitted or defined into existence.
full rationale
The derivation chain is self-contained in the relevant sense. The main abstract theorems (1.13 and 1.14) are obtained from Lemma 3.3, which reduces the coordinate advantage to an expectation of exp<=D(<T,z^⊗p>) over a multinomial vector. Lemma 3.3 invokes Theorem 3.5 and Lemma 4.5 of [Kun24], the author's prior Part I; that is a general overlap bound for product-measure LCDF testing, stated at a level of generality that does not already assert hardness for the GSBMs analyzed here. It is thus a genuine external mathematical input rather than a restatement of the present results. Proposition 3.4 expands the overlap purely by the binomial theorem and the definition of marginal characteristic tensors; no displayed equation defines the target lower bound in terms of itself. The applications compute characteristic tensors and their norms from model parameters in Sections 4.2–4.4 and substitute these computations into the general theorems, so the Kesten-Stigum conditions are consequences rather than assumed inputs. The skeptical note about Section 4.3.2 is a correctness concern about a possible prefactor error and an unverified higher-marginal condition, not an instance of circularity: even if that displayed computation were wrong, the claimed theorem would fail by miscalculation rather than by being equivalent to its inputs. No fitted parameter is renamed as a prediction, and no uniqueness conclusion is imported solely from the author's prior work.
Assumptions & free parameters
assumptions (6)
- domain assumption Non-triviality: some mu_a differs from mu_avg.
- domain assumption Regularity: dmu_a/dmu_avg is in L2(mu_avg) for every a.
- domain assumption Weak symmetry: pairwise L2(mu_avg) inner products of centered likelihood ratios are invariant under simultaneous permutation of the p labels.
- standard math Coordinate advantage bound from [Kun24, Theorem 3.5].
- domain assumption For SBM and HSBM applications, the interaction matrix or tensor has 1 as a Perron-Frobenius eigenvector.
- domain assumption For the sumset application, the group G is abelian.
Cite this review
Pith. "Pith review of Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models." pith.science (2026). https://pith.science/paper/J4X75YUL
@misc{pith2026241221155,
author = {Pith},
title = {Pith review of: Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models},
year = {2026},
howpublished = {\url{https://pith.science/paper/J4X75YUL}},
note = {Machine review of arXiv:2412.21155}
}
abstract
We study when low coordinate degree functions (LCDF) -- linear combinations of functions depending on small subsets of entries of a vector -- can test for the presence of categorical structure, including community structure and generalizations thereof, in high-dimensional data. This complements the first paper of this series, which studied the power of LCDF in testing for continuous structure like real-valued signals perturbed by additive noise. We apply the tools developed there to a general form of stochastic block model (SBM), where a population is assigned random labels and every $p$-tuple of the population generates an observation according to an arbitrary probability measure associated to the $p$ labels of its members. We show that the performance of LCDF admits a unified analysis for this class of models. As applications, we prove tight lower bounds against LCDF (and therefore also against low degree polynomials) for nearly arbitrary graph and regular hypergraph SBMs, always matching suitable generalizations of the Kesten-Stigum threshold. We also prove tight lower bounds for group synchronization and abelian group sumset problems under the "truth-or-Haar" noise model, and use our technical results to give an improved analysis of Gaussian multi-frequency group synchronization. In most of these models, for some parameter settings our lower bounds give new evidence for conjectural statistical-to-computational gaps. Finally, interpreting some of our findings, we propose a precise analogy between categorical and continuous signals: a general SBM as above behaves, in terms of the tradeoff between subexponential runtime cost of testing algorithms and the signal strength needed for a testing algorithm to succeed, like a spiked $p_*$-tensor model of a certain order $p_*$ that may be computed from the parameters of the SBM.
Forward citations
Cited by 1 Pith paper
-
Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.
Reference graph
Works this paper leans on
-
[5]
Non-backtracking spec- trum of random graphs: community detection and non-regular ramanujan graphs
[BLM15] Charles Bordenave, Marc Lelarge, and Laurent Masso uli´ e. Non-backtracking spec- trum of random graphs: community detection and non-regular ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Sci ence, pages 1347–1357. IEEE,
work page 2015
-
[9]
Computational lower bounds for multi-frequency group synchronization
[KBK24] Anastasia Kireeva, Afonso S Bandeira, and Dmitriy K unisky. Computational lower bounds for multi-frequency group synchronization. arXiv preprint arXiv:2406.03424,
-
[12]
Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
[Kun24] Dmitriy Kunisky. Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing. arXiv preprint arXiv:2403.07862 ,
-
[13]
37 [KVWX23] Pravesh K Kothari, Santosh S Vempala, Alexander S W ein, and Jeff Xu. Is planted coloring easier than planted clique? In 36th Annual Conference on Learning Theory (COLT 2023). PMLR,
work page 2023
-
[16]
Optimality and sub-optimality of PCA for spiked random matrices and syn chronization
[PWBM16] Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra. Optimality and sub-optimality of PCA for spiked random matrices and syn chronization. arXiv preprint arXiv:1609.05573,
-
[18]
The Kikuchi hierarchy and tensor PCA
[WEM19] Alexander S Wein, Ahmed El Alaoui, and Cristopher Mo ore. The Kikuchi hierarchy and tensor PCA. arXiv preprint arXiv:1904.03858 ,
arXiv 1904
-
[1984]
[Moo17] Cristopher Moore. The computer science and physics of community detection: land- scapes, phase transitions, and hardness. arXiv preprint arXiv:1702.00467 ,
-
[1986]
The power of sum-of-squares for detecting hidden structures
[HKP+17] Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Pra sad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In 58th Annual Symposium on Foundations of Computer Science (FO CS 2017), pages 720–731,
work page 2017
Show all 19 references
-
[2011]
Spectral de- tection in the censored block model
[SLKZ15] Alaa Saade, Marc Lelarge, Florent Krzakala, and Le nka Zdeborov´ a. Spectral de- tection in the censored block model. In 2015 IEEE International Symposium on Information Theory (ISIT) , pages 1184–1188. IEEE,
2015
-
[2014]
Spectral detection on sparse hypergraphs
[ACKZ15] Maria Chiara Angelini, Francesco Caltagirone, Fl orent Krzakala, and Lenka Zde- borov´ a. Spectral detection on sparse hypergraphs. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton ), pages 66–73. IEEE,
2015
-
[2015]
Empiri cal Bernstein in smooth Ba- nach spaces
[MTR24] Diego Martinez-Taboada and Aaditya Ramdas. Empiri cal Bernstein in smooth Ba- nach spaces. arXiv preprint arXiv:2409.06060 ,
-
[2017]
Community detection in the labelled stochastic block model
[HLM12] Simon Heimlicher, Marc Lelarge, and Laurent Massou li´ e. Community detection in the labelled stochastic block model. arXiv preprint arXiv:1209.2910 ,
-
[2018]
The Franz-Parisi criterion and c omputational trade-offs in high dimensional statistics
[BAH+22] Afonso S Bandeira, Ahmed El Alaoui, Samuel B Hopkins, Tse lil Schramm, Alexan- der S Wein, and Ilias Zadik. The Franz-Parisi criterion and c omputational trade-offs in high dimensional statistics. arXiv preprint arXiv:2205.09727 ,
-
[2019]
Time-uniform self-normalized concentration for vector-valued process es
[WWR23] Justin Whitehouse, Zhiwei Steven Wu, and Aaditya Ra mdas. Time-uniform self-normalized concentration for vector-valued process es. arXiv preprint arXiv:2310.09100,
-
[2020]
Spectral planting and the hardness of refuting cu ts, colorability, and communities in random graphs
[BBK+21] Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Cristop her Moore, and Alexan- der S Wein. Spectral planting and the hardness of refuting cu ts, colorability, and communities in random graphs. In 34th Annual Conference on Learning Theory (COLT 2021), pages 410–473. PMLR,
2021
-
[2021]
Hypothesis testing with low-deg ree polynomials in the Morris class of exponential families
[Kun21a] Dmitriy Kunisky. Hypothesis testing with low-deg ree polynomials in the Morris class of exponential families. In 34th Annual Conference on Learning Theory (COLT 2021), pages 2822–2848. PMLR,
2021
-
[2022]
Statistical query algorithms and low-degree tests are almo st equivalent
[BBH+20] Matthew Brennan, Guy Bresler, Samuel B Hopkins, Jerry Li , and Tselil Schramm. Statistical query algorithms and low-degree tests are almo st equivalent. arXiv preprint arXiv:2009.06107,
2009 arXiv
-
[2023]
Community detection i n the hypergraph stochas- tic block model and reconstruction on hypertrees
[GP24] Yuzhou Gu and Aaradhya Pandey. Community detection i n the hypergraph stochas- tic block model and reconstruction on hypertrees. arXiv preprint arXiv:2402.06856 ,
-
[2024]
Reconstructi on on trees and low-degree polynomials
[KM21] Frederic Koehler and Elchanan Mossel. Reconstructi on on trees and low-degree polynomials. arXiv preprint arXiv:2109.06915 ,
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.