Pith. sign in

REVIEW 1 major objections 3 minor 3 cited by

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

T0 review · 1 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This survey argues that the minimum polynomial degree needed to solve a statistical task tracks its computational difficulty.

desk verdict A transparent, carefully hedged survey that earns its keep as a roadmap, even though the load-bearing degree-runtime heuristic remains informal and its strongest formal version was recently refuted. read the letter →

arxiv 2506.10748 v1 pith:H3HJWE3E submitted 2025-06-12 math.ST cs.CCstat.MLstat.TH

Alexander S. Wein This is my paper · ORCID
classification math.STcs.CCstat.MLstat.TH MSC 68Q1762F0362H12
keywords low-degreepolynomialsstatistical-computationalgapsaverage-casehardnesshypothesistestinghigh-dimensionalstatisticsplantedcliquedegree-runtimecorrespondencelikelihoodratio
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This survey argues that for a broad class of high-dimensional statistical problems, the lowest degree of a polynomial that can solve a task tracks the runtime of the best known algorithms: polynomial-time algorithms correspond to degree $O(\log n)$, and higher degree corresponds to super-polynomial runtime. If this degree-runtime correspondence holds, low-degree lower bounds become a principled way to predict where statistical-computational gaps lie in new problems, even though outright proofs of hardness are out of reach. The paper documents many problems, including planted clique, sparse PCA, tensor PCA, community detection, and random optimization, where low-degree thresholds match the conjectured computational thresholds, and it discusses known counterexamples where the correspondence fails. The survey is careful to distinguish the rigorous parts, which rule out low-degree polynomials, from the heuristic parts, which leap from degree to time complexity.

What carries the argument

The central object is the low-degree polynomial itself, measured by its degree $D$, together with two notions of success: separation for detection, meaning the gap between expectations under the two distributions exceeds the larger standard deviation, and degree-$D$ minimum mean squared error, denoted $\mathrm{MMSE}_{\le D}$, for recovery. The load-bearing quantity for lower bounds is the low-degree advantage $\mathrm{Adv}_{\le D}$, the largest ratio of expected value under the planted distribution to root-mean-square value under the null, taken over all degree-$D$ polynomials; this quantity is computed explicitly by projecting onto an orthonormal polynomial basis for the null distribution. Around this core sit the heuristic degree-runtime correspondence and the low-degree conjecture that aims to formalize the class of problems on which the correspondence should hold.

What would settle it

Exhibit a natural high-dimensional detection problem with a product null distribution and permutation-symmetric planted distribution where the low-degree advantage stays bounded for degree $(\log n)^{1+\epsilon}$ so that low-degree polynomials provably fail, yet a polynomial-time algorithm achieves strong detection with high probability; the known counterexamples in the survey each violate at least one of these conditions, so the falsifier must respect all of them.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that degree complexity, meaning the smallest $D$ such that a degree-$D$ polynomial can weakly or strongly separate planted from null distributions, or achieve small mean squared error in recovery, appears to reliably track time complexity across a wide variety of natural high-dimensional statistical problems. For these problems, the best known polynomial-time algorithms, including spectral methods, message passing, subgraph counts, and local algorithms on sparse graphs, can be implemented by degree-$O(\log n)$ polynomials, and the degree at which polynomials fail coincides with the conjectured computational threshold. The paper therefore proposes the low-degree framework as a unifying explanation for apparent computational barriers and as a tool for making principled predictions about new problems.

Load-bearing premise

The load-bearing premise is that for natural high-dimensional statistical problems, any polynomial-time algorithm can be simulated by a degree-$O(\log n)$ polynomial, and a problem requiring degree $D$ has no algorithm significantly faster than $n^{O(D)}$; this correspondence is heuristic and already has documented exceptions.

Editorial extensions

If this is right

  • If the degree-runtime correspondence is correct, proving that no degree-$O(\log n)$ polynomial separates $P$ from $Q$ becomes standard evidence that no polynomial-time algorithm can strongly detect the planted signal.
  • For recovery, a lower bound of the form $\mathrm{MMSE}_{\le D} \ge (1-o(1))\mathrm{Var}(x)$ at degree $\omega(\log n)$ would indicate that no efficient estimator can beat the trivial guess.
  • The framework extends to four tasks, detection, recovery, optimization, and refutation, allowing it to predict separate computational thresholds for each task, including detection-recovery gaps and detection-refutation gaps.
  • Matching low-degree upper bounds are needed in each regime to confirm that the notion of success is meaningful, and the survey lists several basic cases where these upper bounds are still missing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • As an editorial extension, if the correspondence holds, cryptographic schemes whose security rests on low-degree hardness inherit the caveats of the framework, since known counterexamples such as XOR-SAT and lattice reduction show that noiseless algebraic structure can break low-degree predictions.
  • A testable extension would be to compute $\mathrm{Adv}_{\le D}$ at degree $O(\log n)$ for any new Bayesian high-dimensional inference problem with a product null and permutation-symmetric prior before hunting for algorithms, giving a fast and principled guess about where the computational barrier lies.
  • The known counterexamples suggest that the correspondence is really about robust or noisy settings; one could formalize this by checking whether low-degree predictions survive small resampling noise, thereby separating algebraic easy cases from genuinely hard ones.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. This manuscript is a survey of the low-degree polynomial framework for studying statistical-computational gaps. It introduces the framework, in which polynomial degree serves as a measure of algorithmic complexity; defines notions of success for detection and recovery; states two informal degree-runtime hypotheses; catalogs a long list of success stories across planted problems and non-planted optimization; discusses the recent refutation of Hopkins' conjecture and known counterexamples (XOR-SAT, LLL, error-correcting codes, heavy-tailed noise, small spectral gaps, broadcasting on trees); relates low-degree methods to reductions, sum-of-squares, statistical queries, AMP and statistical physics, and the overlap gap property; and surveys proof techniques and open problems. The paper claims no new theorems; its contribution is an up-to-date, opinionated synthesis of the area.

Significance. If read as a survey, the paper is valuable: it collects definitions, heuristics, results, and caveats in one place and will be a useful reference for entering researchers and for practitioners deciding when to trust low-degree lower bounds. A particular strength is the author's honesty about the limits of the framework: Section 4.3 explicitly states that the standard lower bounds rule out separation but not thresholding, and Section 6.4.2 gives a fair and detailed list of settings where low-degree polynomials are provably beaten by efficient algorithms. The survey also provides a useful taxonomy of tasks (detection, recovery, refutation, optimization) and of connections to other frameworks. Its main weakness is that the central interpretive claim in Section 6.3 is phrased more strongly than the formal status of the degree-runtime correspondence supports; this is a fixable presentation issue rather than a technical error in any of the reported results.

major comments (1)
  1. [Section 6.3] The paragraph following the success-story list states: 'I would consider this a resounding success, in that low-degree polynomials give a unifying explanation for the apparent computational barriers in many different statistical problems, and therefore provide a principled way to predict where the barriers lie in new problems, at least for problems that are similar in style to the examples above.' This is the paper's central interpretive claim, but it is stronger than the evidence reported in the paper itself. Hypotheses 3.1 and 3.2 are explicitly informal; Section 6.4.2 records that the main precise formalization, Hopkins' conjecture, has been refuted by [BHJK25]; and Section 6.4.3 states that a precise characterization of the class of problems for which the correspondence holds is missing. In particular, the phrase 'a principled way to predict' suggests a validated methodology with a known domain of validity, whereas the survey actually documents a well-supported heuristic for problems similar to known success stories, with acknowledged exceptions. I recommend replacing 'resounding success' and 'principled way to predict' with calibrated language such as 'substantial and suggestive body of evidence' and 'a useful heuristic for problems similar in style to those listed, subject to the caveats of Section 6.4.'
minor comments (3)
  1. [Table 1] The caption of Table 1 does not define the checkmark symbols or the two small checkmarks. Please add a sentence explaining that a checkmark means unconditional hardness results exist for that framework-task pair, and clarify the special meaning of the two small marks.
  2. [Section 9, open problem 2] The phrasing 'It may be desirable to rule out other notions of success, such as thresholding' would benefit from an explicit cross-reference to Section 4.3, where the relationship between separation and thresholding is discussed in detail.
  3. [Section 1.2] The sentence 'In contrast to our previous survey [KWB19], this one is mostly non-technical' is slightly misleading, since Part II contains substantial technical discussion, especially Sections 7 and 8. Consider saying 'less technical' or 'more discursive' instead of 'mostly non-technical.'

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the survey reports external, checkable results and explicitly labels its core degree-runtime correspondence as a heuristic.

full rationale

This is a survey rather than a derivation of new hardness results, and its central framework rests on an explicitly informal heuristic rather than on a chain of equations that reduce to themselves. Hypotheses 3.1 and 3.2 are introduced as "informal guiding principle[s]" and are attributed to earlier literature, not proved here; the paper does not define 'success' in terms of the conclusion it draws. The strongest formal version of the low-degree conjecture is reported as refuted by [BHJK25] in Section 6.4.2, and Section 6.4.3 openly states that "describing this class precisely has proven difficult." These admissions weaken the epistemic force of the survey's "principled way to predict" claim, but they are limitations, not circularity. The success-story list is admittedly selected by the criterion that degree complexity should track best-known time complexity, which makes the list illustrative rather than a controlled experiment; however, the underlying low-degree upper and lower bounds are external published theorems with proofs, and the survey does not fit a parameter and then rename that fit as a prediction. The frequent self-citations (e.g., SW22, BKW20, CGH+22) are load-bearing only in the sense that the survey summarizes those results, and those results are independently checkable; no uniqueness theorem or ansatz is imported solely from the author's prior work. No equation in the survey is shown to equal another by construction, and no derived quantity is defined in terms of the target claim. Therefore the paper exhibits no significant circularity.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The survey introduces no fitted parameters and no new entities. It does rest on two working assumptions: the informal degree-runtime correspondence, Hypothesis 3.1/3.2, and the informal notion of a natural high-dimensional statistical problem that delimits where the correspondence is expected to hold. These are stated openly and discussed critically in Sections 6.2 and 6.4.

assumptions (2)
  • ad hoc to paper Degree-runtime correspondence: for natural high-dim stat problems, degree-O(log n) polynomials capture poly-time algorithms, and degree-D polynomials correspond to runtime n^{O(D)} (Hypothesis 3.1 and 3.2).
    This is the central heuristic that makes low-degree lower bounds evidence for computational hardness; it is stated as an informal hypothesis in Section 3.2 and scrutinized in Section 6.
  • domain assumption There is a well-defined class of natural high-dim stat problems for which the degree-runtime correspondence holds.
    The survey relies on an informal class description in Section 2.3 and admits in Section 6.4 that formally defining this class is an open problem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computational Complexity of Statistics: New Insights from Low-Degree Polynomials." pith.science (2026). https://pith.science/paper/H3HJWE3E

@misc{pith2026250610748,
  author       = {Pith},
  title        = {Pith review of: Computational Complexity of Statistics: New Insights from Low-Degree Polynomials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H3HJWE3E}},
  note         = {Machine review of arXiv:2506.10748}
}
read the original abstract

This is a survey on the use of low-degree polynomials to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems. In a nutshell, this framework measures the complexity of a statistical task by the minimum degree that a polynomial function must have in order to solve it. The main goals of this survey are to (1) describe the types of problems where the low-degree framework can be applied, encompassing questions of detection (hypothesis testing), recovery (estimation), and more; (2) discuss some philosophical questions surrounding the interpretation of low-degree lower bounds, and notably the extent to which they should be treated as evidence for inherent computational hardness; (3) explore the known connections between low-degree polynomials and other related approaches such as the sum-of-squares hierarchy and statistical query model; and (4) give an overview of the mathematical tools used to prove low-degree lower bounds. A list of open problems is also included.

Figures

Figures reproduced from arXiv: 2506.10748 by the authors.

Figure 1
Figure 1. Phase diagrams for the two models defined in Section 2.1. [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Formal relations among detection, recovery, and refutation. An arrow [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths

    cs.DS 2026-07 conditional novelty 8.0 of 10

    For any t, directed shortest paths can be computed with near-linear work plus n^{1+o(1)}t^2 work and roughly n/t parallel depth, matching the undirected tradeoff.

  2. The Polynomial-Time Low-Degree Conjecture is False

    cs.CC 2026-07 accept novelty 7.0 of 10

    The polynomial-time low-degree conjecture is false: a permutation-invariant graph distribution with zero low-degree advantage through polylogarithmic degree can still be detected in polynomial time after edge resampling.

  3. High-Dimensional Procrustes Matching via Tree Counts

    stat.ML 2026-07 accept novelty 7.0 of 10

    Exact Procrustes matching of n Gaussian vectors in d≥polylog(n) dimensions is achievable in polynomial time whenever the correlation satisfies ρ²>√α≈0.58, via counting wide trees.

Reference graph

Works this paper leans on

48 extracted references · 17 canonical work pages · cited by 3 Pith papers

  1. [10]

    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 ,

    arXiv

  2. [11]

    Information- computation gaps in quantum learning via low-degree likelihood

    [CGHQ25] Sitan Chen, Weiyuan Gong, Jonas Haferkamp, and Yihui Quek. Information- computation gaps in quantum learning via low-degree likelihood. arXiv preprint arXiv:2505.22743,

    arXiv

  3. [12]

    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,

    arXiv

  4. [13]

    An optimized Franz-Parisi criterion and its equivalence with SQ lower bounds

    [CMZZ25] Siyu Chen, Theodor Misiakiewicz, Ilias Zadik, and Peiyuan Zhang. An optimized Franz-Parisi criterion and its equivalence with SQ lower bounds. arXiv preprint arXiv:2506.06259,

    arXiv

  5. [14]

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

    [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 ,

    arXiv

  6. [15]

    Low-degree hardness of detection for corre- lated Erd˝ os-R´ enyi graphs.arXiv preprint arXiv:2311.15931 ,

    [DDL23] Jian Ding, Hang Du, and Zhangsong Li. Low-degree hardness of detection for corre- lated Erd˝ os-R´ enyi graphs.arXiv preprint arXiv:2311.15931 ,

    arXiv

  7. [17]

    The low-degree hardness of finding large inde- pendent sets in sparse random hypergraphs

    [DW24] Abhishek Dhawan and Yuzhou Wang. The low-degree hardness of finding large inde- pendent sets in sparse random hypergraphs. arXiv preprint arXiv:2404.03842 ,

    work page arXiv

  8. [18]

    Detecting arbitrary planted subgraphs in random graphs

    [EH25] Dor Elimelech and Wasim Huleihel. Detecting arbitrary planted subgraphs in random graphs. arXiv preprint arXiv:2503.19069 ,

    arXiv

Show all 48 references
  1. [20]

    Optimal hardness of online algorithms for large independent sets

    [GKW25] David Gamarnik, Eren C Kızılda˘ g, and Lutz Warnke. Optimal hardness of online algorithms for large independent sets. arXiv preprint arXiv:2504.11450 ,

  2. [21]

    Disordered systems in- sights on computational hardness

    [GMZ22] David Gamarnik, Cristopher Moore, and Lenka Zdeborov´ a. Disordered systems in- sights on computational hardness. Journal of Statistical Mechanics: Theory and Ex- periment, 2022(11):114015,

    2022

  3. [22]

    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 ,

  4. [23]

    Strong low degree hardness for stable local optima in spin glasses

    [HS25a] Brice Huang and Mark Sellke. Strong low degree hardness for stable local optima in spin glasses. arXiv preprint arXiv:2501.06427 ,

  5. [28]

    Sum-of-squares lower bounds for independent set on ultra-sparse random graphs

    [KPX24] Pravesh K Kothari, Aaron Potechin, and Jeff Xu. Sum-of-squares lower bounds for independent set on ultra-sparse random graphs. In ACM Symposium on Theory of Computing, pages 1923–1934,

    1923

  6. [29]

    Spielman, Alexander S

    [KSWY24] Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, and Xifan Yu. Statistical inference of a ranked community in a directed graph.arXiv preprint arXiv:2411.19885,

    arXiv

  7. [30]

    Low coordinate degree algorithms II: Categorical signals and gen- eralized stochastic block models

    [Kun24a] Dmitriy Kunisky. Low coordinate degree algorithms II: Categorical signals and gen- eralized stochastic block models. arXiv preprint arXiv:2412.21155 ,

    arXiv

  8. [31]

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

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

  9. [32]

    A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials

    [Li25b] Zhangsong Li. A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials. arXiv preprint arXiv:2504.03097 ,

  10. [34]

    Almost-optimal local-search methods for sparse tensor PCA

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

    arXiv

  11. [35]

    Optimal clustering by Lloyd algorithm for low-rank mixture model

    [LX22] Zhongyuan Lyu and Dong Xia. Optimal clustering by Lloyd algorithm for low-rank mixture model. arXiv preprint arXiv:2207.04600 ,

    arXiv

  12. [36]

    On the MCMC performance in Bernoulli group testing and the random max set-cover problem

    [LZ24a] Maxwell Lovig and Ilias Zadik. On the MCMC performance in Bernoulli group testing and the random max set-cover problem. arXiv preprint arXiv:2410.09231 ,

    arXiv

  13. [37]

    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 ,

    arXiv

  14. [39]

    Strong low degree hardness for the number parti- tioning problem

    65 [MS25] Rushil Mallarapu and Mark Sellke. Strong low degree hardness for the number parti- tioning problem. arXiv preprint arXiv:2505.20607 ,

    arXiv

  15. [40]

    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,

    arXiv

  16. [41]

    Approximate message passing with spec- tral initialization for generalized linear models

    [MV22] Marco Mondelli and Ramji Venkataramanan. Approximate message passing with spec- tral initialization for generalized linear models. Journal of Statistical Mechanics: The- ory and Experiment , 2022(11):114003,

    2022

  17. [42]

    On optimal distinguishers for planted clique

    [NR25] Ansh Nagda and Prasad Raghavendra. On optimal distinguishers for planted clique. arXiv preprint arXiv:2505.01990 ,

    arXiv

  18. [43]

    Machinery for proving sum-of-squares lower bounds on certification problems

    [PR20] Aaron Potechin and Goutham Rajendran. Machinery for proving sum-of-squares lower bounds on certification problems. arXiv preprint arXiv:2011.04253 ,

    2011 arXiv

  19. [44]

    Tight low degree hardness for optimizing pure spherical spin glasses

    [Sel25] Mark Sellke. Tight low degree hardness for optimizing pure spherical spin glasses. arXiv preprint arXiv:2504.04632 ,

    arXiv

  20. [45]

    Sum-of-squares & gaussian processes I: Certification

    [SS24] Juspreet Singh Sandhu and Jonathan Shi. Sum-of-squares & gaussian processes I: Certification. arXiv preprint arXiv:2401.14383 ,

    arXiv

  21. [46]

    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 ,

    arXiv

  22. [48]

    A concise tutorial on approximate message passing

    [ZY22] Qiuyun Zou and Hongwen Yang. A concise tutorial on approximate message passing. arXiv preprint arXiv:2201.07487 ,

    arXiv

  23. [1976]

    Computational lower bounds for multi-frequency group synchronization

    [KBK24] Anastasia Kireeva, Afonso S Bandeira, and Dmitriy Kunisky. Computational lower bounds for multi-frequency group synchronization. arXiv preprint arXiv:2406.03424 ,

    arXiv

  24. [1985]

    Some easy optimization problems have the overlap-gap property

    [LS24] Shuangping Li and Tselil Schramm. Some easy optimization problems have the overlap-gap property. arXiv preprint arXiv:2411.01836 ,

    arXiv

  25. [2000]

    Fourier analysis of iterative algorithms

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

    arXiv

  26. [2005]

    Near- optimal time-sparsity trade-offs for solving noisy linear equations

    [BBTV24] Kiril Bangachev, Guy Bresler, Stefan Tiegel, and Vinod Vaikuntanathan. Near- optimal time-sparsity trade-offs for solving noisy linear equations. arXiv preprint arXiv:2411.12512,

    arXiv

  27. [2006]

    Sum-of-squares proofs and the quest toward optimal algorithms

    [BS14] Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236 ,

    arXiv

  28. [2008]

    Symmetric perceptrons, number partitioning and lattices

    [VV25] Neekon Vafa and Vinod Vaikuntanathan. Symmetric perceptrons, number partitioning and lattices. arXiv preprint arXiv:2501.16517 ,

    arXiv

  29. [2009]

    A computational transi- tion for detecting correlated stochastic block models by low-degree polynomials

    [CDGL24] Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li. A computational transi- tion for detecting correlated stochastic block models by low-degree polynomials. arXiv preprint arXiv:2409.00966,

  30. [2011]

    The LASSO risk for Gaussian matrices

    [BM11b] Mohsen Bayati and Andrea Montanari. The LASSO risk for Gaussian matrices. IEEE Transactions on Information Theory , 58(4):1997–2017,

    1997

  31. [2016]

    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,

    1939

  32. [2017]

    Algorithmic thresholds for tensor PCA

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

  33. [2018]

    Fast, robust approximate message passing

    [IS24a] Misha Ivkov and Tselil Schramm. Fast, robust approximate message passing. arXiv preprint arXiv:2411.02764,

    arXiv

  34. [2019]

    Approximate message-passing for convex optimization with non-separable penalties

    [MKV+18] Andre Manoel, Florent Krzakala, Ga¨ el Varoquaux, Bertrand Thirion, and Lenka Zde- borov´ a. Approximate message-passing for convex optimization with non-separable penalties. arXiv preprint arXiv:1809.06304 ,

    arXiv

  35. [2020]

    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,

    arXiv

  36. [2021]

    Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes

    [Gam25] David Gamarnik. Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes. arXiv preprint arXiv:2501.15312 ,

    arXiv

  37. [2022]

    Computational equivalence of spiked covari- ance and spiked Wigner models via Gram-Schmidt perturbation

    [BH25] Guy Bresler and Alina Harbuzova. Computational equivalence of spiked covari- ance and spiked Wigner models via Gram-Schmidt perturbation. arXiv preprint arXiv:2503.02802,

    arXiv

  38. [2023]

    Algorithms approaching the threshold for semi-random planted clique

    53 [BKS23] Rares-Darius Buhai, Pravesh K Kothari, and David Steurer. Algorithms approaching the threshold for semi-random planted clique. In ACM Symposium on Theory of Computing, pages 1918–1926,

    1918

  39. [2024]

    Detecting correlation efficiently in stochastic block models: breaking Otter’s threshold by counting decorated trees

    [CDGL25] Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li. Detecting correlation efficiently in stochastic block models: breaking Otter’s threshold by counting decorated trees. arXiv preprint arXiv:2503.06464 ,

  40. [2025]

    The quasi- polynomial low-degree conjecture is false

    [BHJK25] Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, and Pravesh K Kothari. The quasi- polynomial low-degree conjecture is false. arXiv preprint arXiv:2505.17360 ,

    arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.