pith. sign in

arxiv: 2605.30113 · v1 · pith:U7GS5SXSnew · submitted 2026-05-28 · 🧮 math.ST · cs.CC· cs.DS· math.PR· stat.TH

Low-degree estimation thresholds in planted hypergraphs and tensor PCA

Daniel Fu , Youngtak Sohn This is my paper

Pith reviewed 2026-06-29 00:00 UTC · model grok-4.3

classification 🧮 math.ST cs.CCcs.DSmath.PRstat.TH
keywords low-degree estimationplanted dense subhypergraphtensor PCAsharp thresholdstatistical-computational gaphigh-dimensional statisticsrecovery algorithmspolynomial estimators
0
0 comments X

The pith

In planted dense subhypergraphs with hidden set larger than sqrt(n), low-degree estimation has a sharp threshold.

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

This paper identifies sharp thresholds for when low-degree polynomial estimators can recover hidden planted structures in hypergraph and tensor models. For planted dense subhypergraphs, when the hidden vertex set exceeds size sqrt(n), low-degree methods succeed above a certain signal strength and fail below it. Below the sqrt(n) scale, it shows that low-degree methods are hard in the regimes expected from earlier predictions. The work also finds similar transitions in sparse tensor PCA and establishes matching lower bounds for tensor PCA under general priors. These findings clarify the boundary between what low-degree methods can achieve and where computational gaps appear in high-dimensional inference.

Core claim

The paper shows that in the planted dense subhypergraph model on n vertices, there exist two regimes split by the sqrt(n) scale for the planted set size. Above this scale, a sharp threshold governs low-degree estimation success. Below it, hardness is proven for low-degree methods. Analogous sharp phase transitions hold for sparse tensor PCA. For tensor PCA with general priors, a low-degree lower bound is proven at the critical signal scale, and the lower bounds hold for degrees up to n to a constant power, with matching upper bounds that yield efficient algorithms above the threshold in the larger-set regime.

What carries the argument

a conditional variant of the low-degree analysis framework that yields the correct signal-to-noise ratio

If this is right

  • Polynomial-time algorithms achieve almost exact recovery above the identified threshold in planted dense subhypergraphs and sparse tensor PCA when the planted set is larger than sqrt(n).
  • Low-degree lower bounds apply up to degree n to a positive constant power.
  • The results establish hardness for low-degree methods below the sqrt(n) scale in the predicted regimes.
  • For tensor PCA with a general prior, the low-degree bound matches the degree-signal tradeoff at the critical scale.

Where Pith is reading between the lines

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

  • The sqrt(n) scale may mark a transition point where different analysis techniques become necessary in other planted models.
  • These thresholds could guide the search for algorithms that surpass low-degree limitations in the hard regimes.
  • The conditional analysis approach might apply to additional high-dimensional statistical problems involving tensors or hypergraphs.
  • It raises the question of whether information-theoretic recovery remains possible in the regimes where low-degree methods fail.

Load-bearing premise

The conditional variant of the low-degree analysis accurately identifies the signal-to-noise ratio in settings where the standard approach does not suffice.

What would settle it

An explicit computation or simulation of the expected correlation of a degree-D polynomial with the hidden signal in the planted dense subhypergraph model, checking whether it crosses from below to above the detection threshold exactly at the claimed critical signal strength.

Figures

Figures reproduced from arXiv: 2605.30113 by Daniel Fu, Youngtak Sohn.

Figure 1
Figure 1. Figure 1: Schematic of a hypertree in T6 for r = 3 and ℓ = 6. Vertices are represented by filled dots and edges by enclosed circles. The root vertex and its root-incident edges are highlighted in red. Algorithm 1 Almost-exact recovery via color-coding for planted dense subhypergraph. 1: Input: Adjacency tensor Y , parameters ρ, q0, q1, ε, and degree parameter ℓ. 2: Preprocessing: Set λ = √ q1−q0 q0(1−q0) , λ⋆ = q(r−… view at source ↗
read the original abstract

A central question in high-dimensional statistics is to understand statistical--computational gaps: regimes in which recovering a hidden signal is information-theoretically possible but conjectured to be computationally intractable. The low-degree framework offers a concrete way to study this gap by restricting attention to estimators that are polynomials of degree at most $D$ in the observed data. In this paper, we study low-degree estimation in planted dense subhypergraph, sparse tensor PCA, and tensor PCA with a general prior. For the planted dense subhypergraph model on $n$ vertices, we identify two regimes depending on whether the planted set is larger or smaller than $\sqrt{n}$. Above this scale, we identify a sharp threshold for low-degree estimation. Below this scale, we establish hardness in the regimes predicted by prior work, thereby resolving a question of Schramm and Wein (2022) and Sohn and Wein (2025). For sparse tensor PCA, we identify an analogous sharp phase transition. For tensor PCA with a general prior, we prove a low-degree estimation lower bound at the critical signal scale, matching the degree--signal tradeoff suggested by prior work. Our lower bounds apply to degree $D=n^{\delta}$, where $n$ is the dimension and $\delta>0$ is a constant, and we complement them with corresponding low-degree upper bounds. In addition, for planted dense subhypergraph and sparse tensor PCA above the $\sqrt{n}$ scale, we convert our upper bounds into polynomial-time algorithms that achieve almost exact recovery above the sharp threshold, yielding polynomial-time algorithms succeeding up to this threshold. Our proofs extend the framework of Sohn and Wein (2025) through a conditional variant that yields the correct signal-to-noise ratio in settings where the unconditional approach is insufficient.

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 paper studies low-degree estimation thresholds in the planted dense subhypergraph model on n vertices (distinguishing regimes above and below the √n scale for the planted set), sparse tensor PCA, and tensor PCA with general priors. Above √n it identifies a sharp threshold for low-degree estimation and converts the matching upper bounds into polynomial-time algorithms for almost exact recovery; below √n it establishes hardness, resolving questions left open by Schramm-Wein (2022) and Sohn-Wein (2025). Analogous sharp transitions are obtained for sparse tensor PCA, while a low-degree lower bound is proved for the general-prior tensor PCA model at the critical signal scale. All lower bounds hold for degree D = n^δ (δ > 0 constant) and rely on a conditional variant of the Sohn-Wein (2025) framework that is claimed to produce the correct signal-to-noise ratio where the unconditional approach is insufficient.

Significance. If the conditional extension is rigorously justified, the results would resolve concrete open questions on computational-statistical gaps in hypergraph and tensor models, supply both matching lower and upper bounds, and yield explicit polynomial-time algorithms up to the identified thresholds. The work thereby strengthens the low-degree framework by demonstrating how a conditional variant can be used to obtain tight thresholds in regimes where prior unconditional analyses were inconclusive.

minor comments (2)
  1. [Abstract] The abstract states that the conditional variant 'yields the correct signal-to-noise ratio' but does not indicate where in the manuscript the verification that this variant preserves the original threshold (rather than shifting it) is carried out; a short pointer to the relevant lemma or proposition would help readers.
  2. The phrase 'almost exact recovery' is used for the algorithmic results above the threshold; a precise definition (e.g., in terms of overlap or Hamming error) should appear in the introduction or the statement of the algorithmic theorem.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our work, including the recommendation for minor revision. We are glad that the contributions toward resolving open questions from Schramm-Wein (2022) and Sohn-Wein (2025) via the conditional low-degree framework are viewed as significant. Below we address the sole substantive point raised regarding justification of the conditional extension.

read point-by-point responses

  1. Referee: If the conditional extension is rigorously justified, the results would resolve concrete open questions on computational-statistical gaps in hypergraph and tensor models, supply both matching lower and upper bounds, and yield explicit polynomial-time algorithms up to the identified thresholds. The work thereby strengthens the low-degree framework by demonstrating how a conditional variant can be used to obtain tight thresholds in regimes where prior unconditional analyses were inconclusive.

    Authors: We appreciate this observation. The manuscript already contains a self-contained rigorous development of the conditional variant (see Section 3 and the proofs in Sections 4–6). The conditional framework is defined via an explicit conditioning on a high-probability event that preserves the relevant moments while allowing the low-degree likelihood ratio to be computed exactly; all steps are deterministic and do not rely on unproven heuristics. This yields the sharp thresholds stated in Theorems 1.1, 1.3, and 1.5. We are happy to add a short clarifying paragraph in the introduction if the referee believes it would further emphasize the distinction from the unconditional approach. revision: partial

Circularity Check

1 steps flagged

Central results rely on conditional extension of same-author prior framework

specific steps
  1. self citation load bearing [Abstract (final paragraph)]
    "Our proofs extend the framework of Sohn and Wein (2025) through a conditional variant that yields the correct signal-to-noise ratio in settings where the unconditional approach is insufficient."

    The sharp low-degree thresholds, hardness below √n, and polynomial-time algorithms are established by extending the cited framework from overlapping authors; the conditional variant supplies the key SNR that the unconditional version lacks, so the central claims rest on this self-citation chain.

full rationale

The abstract states that proofs extend the Sohn and Wein (2025) framework (overlapping authors) via a conditional variant to obtain the correct SNR. This makes the load-bearing derivation of thresholds and hardness results dependent on the self-cited prior work. No equations or reductions to fitted inputs are visible, and the central claim retains independent content in the new regimes and algorithms, so the circularity is moderate rather than forcing the result by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on abstract only; no specific free parameters, axioms, or invented entities are detailed in the provided text.

pith-pipeline@v0.9.1-grok · 5886 in / 793 out tokens · 38037 ms · 2026-06-29T00:00:18.917960+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

19 extracted references · 16 canonical work pages · 5 internal anchors

  1. [1]

    Algorithmic thresholds for tensor PCA.The Annals of Probability, 48(4):2052–2087,

    [BGJ20] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor PCA.The Annals of Probability, 48(4):2052–2087,

    2052

  2. [2]

    arXiv preprint arXiv:2509.09353 , year=

    [CGGV25] Alexandra Carpentier, Simone Maria Giancola, Christophe Giraud, and Nicolas Verzelen. Low-degree lower bounds via almost orthonormal bases.arXiv preprint arXiv:2509.09353,

    work page arXiv

  3. [3]

    Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities

    [CGV25] Alexandra Carpentier, Christophe Giraud, and Nicolas Verzelen. Phase transi- tion for stochastic block model with more than √n communities.arXiv preprint arXiv:2509.15822,

    work page internal anchor Pith review Pith/arXiv arXiv

  4. [4]

    Stochastic block models with many communities and the Kesten–Stigum bound.arXiv preprint arXiv:2503.03047,

    [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

  5. [5]

    On the low-temperature mcmc threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule

    63 [CSZ24] Zongchen Chen, Conor Sheehan, and Ilias Zadik. On the low-temperature mcmc threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule. arXiv preprint arXiv:2408.00746,

    work page arXiv

  6. [6]

    The landscape of the planted clique problem: Dense subgraphs and the overlap gap property.arXiv preprint arXiv:1904.07174,

    64 [GZ19] David Gamarnik and Ilias Zadik. The landscape of the planted clique problem: Dense subgraphs and the overlap gap property.arXiv preprint arXiv:1904.07174,

    work page arXiv 1904

  7. [7]

    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

  8. [8]

    arXiv preprint arXiv:2502.04861 , year=

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

    work page arXiv

  9. [9]

    Statistical thresholds for tensor PCA.Annals of Applied Probability, 30(4):1910–1933,

    [JLM20] Aukosh Jagannath, Patrick Lopatto, and L´ eo Miolane. Statistical thresholds for tensor PCA.Annals of Applied Probability, 30(4):1910–1933,

    1910

  10. [10]

    [KS66] H

    arXiv version available at arXiv:2404.18735. [KS66] H. Kesten and B. P. Stigum. Additional limit theorems for indecomposable multidi- mensional Galton-Watson processes.Ann. Math. Statist., 37:1463–1481,

    work page arXiv

  11. [11]

    A note on Pr\"ufer-like coding and counting forests of uniform hypertrees

    65 [Lav11] Christian Lavault. A note on pr¨ ufer-like coding and counting forests of uniform hypertrees.arXiv preprint arXiv:1110.0204,

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    A smooth computational transition in tensor pca.arXiv preprint arXiv:2509.09904,

    [Li25] Zhangsong Li. A smooth computational transition in tensor pca.arXiv preprint arXiv:2509.09904,

    work page arXiv

  13. [13]

    Almost-optimal local-search methods for sparse tensor PCA.arXiv preprint arXiv:2506.09959,

    [LSTZ25] Max Lovig, Conor Sheehan, Konstantinos Tsirkas, and Ilias Zadik. Almost-optimal local-search methods for sparse tensor PCA.arXiv preprint arXiv:2506.09959,

    work page arXiv

  14. [14]

    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

  15. [15]

    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. InProceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3389–3423. World Scientific,

    2018

  16. [16]

    Sharp Phase Transitions in Estimation with Low-Degree Polynomials

    [SW25] Youngtak Sohn and Alexander S Wein. Sharp phase transitions in estimation with low-degree polynomials.arXiv preprint arXiv:2502.14407,

    work page internal anchor Pith review Pith/arXiv arXiv

  17. [17]

    Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors

    [THZ26] Runshi Tang, Yuefeng Han, and Anru R Zhang. Detection is harder than estimation in certain regimes: Inference for moment and cumulant tensors.arXiv preprint arXiv:2603.26029,

    work page internal anchor Pith review Pith/arXiv arXiv

  18. [18]

    Tsirkas, L

    [TWZ26] Konstantinos Tsirkas, Leda Wang, and Ilias Zadik. The monotonicity of the franz- parisi potential is equivalent with low-degree MMSE lower bounds.arXiv preprint arXiv:2603.20070,

    work page arXiv

  19. [19]

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

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

    work page arXiv