pith. sign in

arxiv: 2502.14407 · v3 · pith:ABOCQF77new · submitted 2025-02-20 · 🧮 math.ST · cs.CC· cs.DS· math.PR· stat.TH

Sharp Phase Transitions in Estimation with Low-Degree Polynomials

Youngtak Sohn , Alexander S. Wein This is my paper

Pith reviewed 2026-05-23 02:52 UTC · model grok-4.3

classification 🧮 math.ST cs.CCcs.DSmath.PRstat.TH
keywords low-degree polynomialsplanted submatrixspiked Wigner modelstochastic block modelphase transitionsestimationcomputational hardnessBBP transition
0
0 comments X

The pith

Low-degree polynomials of degree n to a positive constant power cannot achieve consistent estimation below sharp thresholds such as the BBP transition or Kesten-Stigum threshold in planted high-dimensional problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that in the planted submatrix, planted dense subgraph, spiked Wigner, and stochastic block models, no low-degree polynomial estimator of degree n^δ succeeds at recovering the hidden structure below certain phase transitions. These bounds are sharp, matching known statistical thresholds or conjectured computational barriers, and apply to estimation rather than only hypothesis testing. The results improve on prior work by handling polynomials whose degree grows as a positive power of the dimension n and resolve specific open questions about the reach of this algorithmic class.

Core claim

Low-degree polynomial estimators of degree up to n^δ for any constant δ > 0 cannot perform consistent estimation of the planted signal below the BBP transition in the spiked Wigner model, below the Kesten-Stigum threshold in the stochastic block model, and at analogous sharp thresholds in the planted submatrix and dense subgraph problems; in several cases the optimal exponent δ is identified exactly.

What carries the argument

Lower-bound techniques on the correlation or risk of degree-n^δ polynomial estimators that establish sharp impossibility thresholds for estimation tasks.

If this is right

  • Estimation below the BBP transition is impossible for any polynomial of degree n^δ in the spiked Wigner model.
  • Community detection below the Kesten-Stigum threshold is impossible for any polynomial of degree n^δ in the stochastic block model.
  • The same style of sharp impossibility holds for planted submatrix and dense subgraph recovery.
  • The optimal degree threshold δ is pinned down exactly in some of the models.
  • These bounds supply rigorous low-degree evidence for conjectures on computational-statistical gaps in the cited models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If low-degree polynomials capture the full power of efficient algorithms, the derived thresholds mark the onset of computational intractability rather than merely statistical impossibility.
  • The new proof techniques for sharp estimation bounds may transfer to other planted or spiked models that exhibit similar gaps.
  • Algorithms that succeed below the thresholds must necessarily use operations outside the low-degree polynomial class.

Load-bearing premise

That failure of low-degree polynomials to succeed at estimation is a reliable indicator of computational hardness for general efficient algorithms.

What would settle it

An explicit polynomial-time algorithm (outside the low-degree class) that achieves consistent estimation below one of the stated thresholds in the spiked Wigner model or stochastic block model.

read the original abstract

High-dimensional planted problems, such as finding a hidden dense subgraph within a random graph, often exhibit a gap between statistical and computational feasibility. While recovering the hidden structure may be statistically possible, it is conjectured to be computationally intractable in certain parameter regimes. A powerful approach to understanding this hardness involves proving lower bounds on the efficacy of low-degree polynomial algorithms. We introduce new techniques for establishing such lower bounds, leading to novel results across diverse settings: planted submatrix, planted dense subgraph, the spiked Wigner model, and the stochastic block model. Notably, our results address the estimation task -- whereas most prior work is limited to hypothesis testing -- and capture sharp phase transitions such as the "BBP" transition in the spiked Wigner model (named for Baik, Ben Arous, and P\'{e}ch\'{e}) and the Kesten-Stigum threshold in the stochastic block model. Existing work on estimation either falls short of achieving these sharp thresholds or is limited to polynomials of very low (constant or logarithmic) degree. In contrast, our results rule out estimation with polynomials of degree $n^{\delta}$ where $n$ is the dimension and $\delta > 0$ is a constant, and in some cases we pin down the optimal constant $\delta$. Our work resolves open problems posed by Hopkins & Steurer (2017) and Schramm & Wein (2022), and provides rigorous support within the low-degree framework for conjectures by Abbe & Sandon (2018) and Lelarge & Miolane (2019).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces new analytic techniques for proving lower bounds against low-degree polynomial estimators in high-dimensional planted problems (planted submatrix, planted dense subgraph, spiked Wigner, stochastic block model). It extends the low-degree method from hypothesis testing to the estimation task and obtains sharp thresholds, including the BBP transition in the spiked Wigner model and the Kesten-Stigum threshold in the SBM; the results rule out nontrivial estimation by degree-n^δ polynomials for constant δ>0 (and in some cases identify the optimal δ), thereby resolving open questions of Hopkins & Steurer (2017) and Schramm & Wein (2022).

Significance. If the claimed sharp thresholds hold, the work supplies the first low-degree lower bounds that reach the information-theoretic transitions for estimation (rather than testing) and that apply to polynomials whose degree grows as a positive power of n. This strengthens the low-degree framework as a computationally relevant proxy and gives rigorous backing, inside that framework, to the conjectures of Abbe & Sandon (2018) and Lelarge & Miolane (2019). The explicit resolution of the two cited open problems is a clear contribution.

minor comments (2)
  1. [Abstract / §1] The abstract states that the new techniques 'capture sharp phase transitions' but does not indicate in which section the main technical innovation (the analytic device that reaches the BBP/Kesten-Stigum thresholds for estimation) is introduced; a brief roadmap paragraph in §1 would help readers locate the key argument.
  2. [Theorem statements] Notation for the degree exponent δ is introduced in the abstract but the precise dependence of the allowed degree on the model parameters is not restated when the main theorems are stated; adding a uniform sentence in each theorem statement would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report, accurate summary of our contributions, and recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives lower bounds on low-degree polynomial estimation via new analytic techniques applied directly to the model definitions (planted submatrix, spiked Wigner, SBM). These are mathematical statements about the non-existence of certain polynomials below explicit thresholds (BBP, Kesten-Stigum), obtained from first-principles analysis rather than any fitted parameter, self-definition, or reduction to prior self-citations. The cited open problems (Hopkins-Steurer 2017, Schramm-Wein 2022) are resolved by the new proofs; the self-citation is not load-bearing for the central claims, which remain externally falsifiable via the explicit degree-n^δ bounds and threshold calculations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard tools from probability theory (moment calculations, concentration) and the established low-degree framework; no free parameters, ad-hoc axioms, or invented entities appear in the abstract.

axioms (1)
  • standard math Standard concentration inequalities and moment bounds for random matrices and graphs hold in the high-dimensional regime
    Invoked implicitly when analyzing the performance of low-degree polynomials on planted models.

pith-pipeline@v0.9.0 · 5822 in / 1345 out tokens · 42209 ms · 2026-05-23T02:52:10.709129+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · 5 internal anchors

  1. [1]

    Community Detection in Random Networks

    [ACV13] Ery Arias-Castro and Nicolas Verzelen. Community detection in random networks. arXiv preprint arXiv:1302.7099 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  2. [2]

    Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation

    [Ame13] Brendan PW Ames. Robust convex relaxation for the planted clique and densest k-subgraph problems. arXiv preprint arXiv:1305.4891 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    Crossing the KS threshold in the stochastic block model with information theory

    57 [AS16] Emmanuel Abbe and Colin Sandon. Crossing the KS threshold in the stochastic block model with information theory. In 2016 IEEE International Symposium on Information Theory (ISIT) , pages 840–844. IEEE,

    work page 2016

  4. [4]

    A multiscale cavity method for sublinear-rank symmetric matrix factorization

    [BKR24] Jean Barbier, Justin Ko, and Anas A Rahman. A multiscale cavity method for sublinear-rank symmetric matrix factorization. arXiv preprint arXiv:2403.07189,

    work page arXiv

  5. [5]

    Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs

    [BLM15b] Charles Bordenave, Marc Lelarge, and Laurent Massouli´ e. Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347–1357. IEEE,

    work page 2015

  6. [6]

    Algorithmic universality, low-degree poly- nomials, and max-cut in sparse random graphs

    [CG24] Houssam El Cheairi and David Gamarnik. Algorithmic universality, low-degree poly- nomials, and max-cut in sparse random graphs. arXiv preprint arXiv:2412.18014 ,

    work page arXiv

  7. [7]

    Stochastic block models with many communities and the Kesten–Stigum bound

    [CMSW25] Byron Chin, Elchanan Mossel, Youngtak Sohn, and Alexander S Wein. Stochastic block models with many communities and the Kesten–Stigum bound. arXiv preprint arXiv:2503.03047,

    work page arXiv

  8. [8]

    Low degree conjecture implies sharp computational thresholds in stochastic block model

    [DHSS25] Jingqiu Ding, Yiding Hua, Lucas Slot, and David Steurer. Low degree conjecture implies sharp computational thresholds in stochastic block model. arXiv preprint arXiv:2502.15024,

    work page arXiv

  9. [9]

    Information-theoretically optimal sparse PCA

    [DM14] Yash Deshpande and Andrea Montanari. Information-theoretically optimal sparse PCA. In 2014 IEEE International Symposium on Information Theory , pages 2197–

    work page 2014

  10. [10]

    Detection of dense subhyper- graphs by low-degree polynomials

    [DMW23] Abhishek Dhawan, Cheng Mao, and Alexander S Wein. Detection of dense subhyper- graphs by low-degree polynomials. arXiv preprint arXiv:2304.08135 ,

    work page arXiv

  11. [11]

    Computational lower bounds in latent models: clustering, sparse-clustering, biclustering

    [EGV25] Bertrand Even, Christophe Giraud, and Nicolas Verzelen. Computational lower bounds in latent models: clustering, sparse-clustering, biclustering. arXiv preprint arXiv:2506.13647,

    work page arXiv

  12. [12]

    Low degree hardness for broadcasting on trees

    [HM24] Han Huang and Elchanan Mossel. Low degree hardness for broadcasting on trees. arXiv preprint arXiv:2402.13359 ,

    work page arXiv

  13. [13]

    Optimal low degree hardness for broadcasting on trees

    [HM25] Han Huang and Elchanan Mossel. Optimal low degree hardness for broadcasting on trees. arXiv preprint arXiv:2502.04861 ,

    work page arXiv

  14. [14]

    A greedy anytime algorithm for sparse pca

    [HSV20] Guy Holtzman, Adam Soffer, and Dan Vilenchik. A greedy anytime algorithm for sparse pca. In Conference on Learning Theory, pages 1939–1956. PMLR,

    work page 1939

  15. [15]

    Fourier analysis of iterative algorithms

    [JP24] Chris Jones and Lucas Pesenti. Fourier analysis of iterative algorithms. arXiv preprint arXiv:2404.07881,

    work page arXiv

  16. [16]

    Reconstruction on trees and low-degree poly- nomials

    [KM21] Frederic Koehler and Elchanan Mossel. Reconstruction on trees and low-degree poly- nomials. arXiv preprint arXiv:2109.06915 ,

    work page arXiv

  17. [17]

    Tensor cumulants for statistical inference on invariant distributions

    [KMW24] Dmitriy Kunisky, Cristopher Moore, and Alexander S Wein. Tensor cumulants for statistical inference on invariant distributions. arXiv preprint arXiv:2404.18735,

    work page arXiv

  18. [18]

    Mutual information in rank-one matrix estimation

    [KXZ16] Florent Krzakala, Jiaming Xu, and Lenka Zdeborov´ a. Mutual information in rank-one matrix estimation. In 2016 IEEE Information Theory Workshop (ITW) , pages 71–75. IEEE,

    work page 2016

  19. [19]

    Computational lower bounds for graphon estimation via low-degree polynomials

    [LG23] Yuetian Luo and Chao Gao. Computational lower bounds for graphon estimation via low-degree polynomials. arXiv preprint arXiv:2308.15728 ,

    work page arXiv

  20. [20]

    Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs

    [Li25] Zhangsong Li. Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs. arXiv preprint arXiv:2502.09832 ,

    work page arXiv

  21. [21]

    MMSE of probabilistic low- rank matrix estimation: Universality with respect to the output channel

    [LKZ15a] Thibault Lesieur, Florent Krzakala, and Lenka Zdeborov´ a. MMSE of probabilistic low- rank matrix estimation: Universality with respect to the output channel. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages 680–687. IEEE,

    work page 2015

  22. [22]

    Phase transitions in spiked matrix estimation: information-theoretic analysis

    [Mio18] L´ eo Miolane. Phase transitions in spiked matrix estimation: information-theoretic analysis. arXiv preprint arXiv:1806.04343 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  23. [23]

    Perturba- tive construction of mean-field equations in extensive-rank matrix factorization and denoising

    [MKMZ22] Antoine Maillard, Florent Krzakala, Marc M´ ezard, and Lenka Zdeborov´ a. Perturba- tive construction of mean-field equations in extensive-rank matrix factorization and denoising. Journal of Statistical Mechanics: Theory and Experiment , 2022(8):083301,

    work page 2022

  24. [24]

    Stochastic Block Models and Reconstruction

    [MNS12] Elchanan Mossel, Joe Neeman, and Allan Sly. Stochastic block models and reconstruc- tion. arXiv preprint arXiv:1202.1499 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  25. [25]

    The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

    [Moo17] Cristopher Moore. The computer science and physics of community detection: Land- scapes, phase transitions, and hardness. arXiv preprint arXiv:1702.00467 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  26. [26]

    Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs

    [MSS24] Elchanan Mossel, Allan Sly, and Youngtak Sohn. Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs. arXiv preprint arXiv:2406.15957,

    work page arXiv

  27. [27]

    Testing network correlation efficiently via counting trees

    [MWXY21] Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H Yu. Testing network correlation efficiently via counting trees. arXiv preprint arXiv:2110.11816 ,

    work page arXiv

  28. [28]

    Spectral clustering and the high- dimensional stochastic blockmodel

    [RCY11] Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high- dimensional stochastic blockmodel. The Annals of Statistics , 39(4):1878–1915,

    work page 1915

  29. [29]

    High dimensional esti- mation via sum-of-squares proofs

    [RSS18] Prasad Raghavendra, Tselil Schramm, and David Steurer. High dimensional esti- mation via sum-of-squares proofs. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018 , pages 3389–3423. World Scientific,

    work page 2018

  30. [30]

    Computational complexity of statistics: New insights from low- degree polynomials

    64 [Wei25] Alexander S Wein. Computational complexity of statistics: New insights from low- degree polynomials. arXiv preprint arXiv:2506.10748 ,

    work page arXiv

  31. [31]

    The Kikuchi hierarchy and tensor PCA

    [WEM19] Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi hierarchy and tensor PCA. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1446–1468. IEEE,

    work page 2019

  32. [32]

    Counting stars is constant-degree optimal for detecting any planted subgraph

    [YZZ24] Xifan Yu, Ilias Zadik, and Peiyuan Zhang. Counting stars is constant-degree optimal for detecting any planted subgraph. arXiv preprint arXiv:2403.17766 ,

    work page arXiv