pith. sign in

arxiv: 1907.11636 · v1 · pith:32IRDUFVnew · submitted 2019-07-26 · 🧮 math.ST · cs.CC· cs.DS· stat.ML· stat.TH

Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

Dmitriy Kunisky , Alexander S. Wein , Afonso S. Bandeira This is my paper

Pith reviewed 2026-05-24 15:06 UTC · model grok-4.3

classification 🧮 math.ST cs.CCcs.DSstat.MLstat.TH
keywords low-degree likelihood ratiocomputational hardnesshypothesis testingsum-of-squarestensor PCAstatistical inferencespectral methods
0
0 comments X

The pith

The second moment of the low-degree likelihood ratio predicts the computational time needed to solve hypothesis testing problems.

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

The paper surveys the low-degree method for predicting statistical-versus-computational tradeoffs in high-dimensional inference. The method uses the second moment of the low-degree likelihood ratio to indicate how much computation is required to distinguish between hypotheses. This provides a way to forecast when statistical inference tasks will be computationally hard even if information-theoretically possible. The notes include new results such as a connection to spectral methods and a sharp bound for tensor PCA.

Core claim

The low-degree method posits that the second moment of the low-degree likelihood ratio gives insight into the computational time required to solve a hypothesis testing problem, allowing predictions of computational hardness for statistical inference tasks.

What carries the argument

The second moment of the low-degree likelihood ratio, which quantifies the power of low-degree polynomial tests to distinguish the null and alternative hypotheses.

If this is right

  • The method yields a sharp low-degree lower bound against subexponential-time algorithms for tensor PCA.
  • It establishes a formal connection between spectral methods and the low-degree likelihood ratio.
  • Predictions from the method can be applied to a variety of statistical inference tasks to identify computational barriers.
  • It supports both rigorous and conjectural consequences for understanding computational hardness.

Where Pith is reading between the lines

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

  • If the predictor holds, it could guide the search for efficient algorithms by identifying when they are unlikely to exist.
  • The approach might extend to predict hardness in optimization problems beyond hypothesis testing.
  • Validating the predictions on additional problems could strengthen or challenge the conjectural aspects.

Load-bearing premise

The second moment of the low-degree likelihood ratio serves as a reliable predictor of computational hardness for hypothesis testing problems.

What would settle it

Finding a hypothesis testing problem where an efficient algorithm succeeds despite a large second moment of the low-degree likelihood ratio, or where the moment is small but no efficient algorithm exists.

read the original abstract

These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensional inference problems. In short, the method posits that a certain quantity -- the second moment of the low-degree likelihood ratio -- gives insight into how much computational time is required to solve a given hypothesis testing problem, which can in turn be used to predict the computational hardness of a variety of statistical inference tasks. While this method originated in the study of the sum-of-squares (SoS) hierarchy of convex programs, we present a self-contained introduction that does not require knowledge of SoS. In addition to showing how to carry out predictions using the method, we include a discussion investigating both rigorous and conjectural consequences of these predictions. These notes include some new results, simplified proofs, and refined conjectures. For instance, we point out a formal connection between spectral methods and the low-degree likelihood ratio, and we give a sharp low-degree lower bound against subexponential-time algorithms for tensor PCA.

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

2 major / 3 minor

Summary. The manuscript is a survey of the low-degree method for predicting statistical-versus-computational tradeoffs in high-dimensional hypothesis testing. The central posit is that the second moment of the low-degree likelihood ratio provides insight into the computational time required for a given testing problem; the notes present a self-contained introduction, distinguish rigorous results (e.g., spectral-method connection and sharp tensor-PCA lower bound) from conjectural predictions, and include new results plus refined conjectures.

Significance. If the posited link holds, the method supplies a practical heuristic for mapping computational-statistical gaps across inference tasks, extending sum-of-squares ideas in an accessible form. The explicit separation of rigorous theorems (including the tensor-PCA bound) from conjectures, together with simplified proofs, adds value as a reference for researchers studying average-case hardness.

major comments (2)
  1. [Introduction / spectral-methods section] The abstract and introduction claim a 'formal connection between spectral methods and the low-degree likelihood ratio' as a rigorous new result. The manuscript should state the precise theorem (including any equation defining the low-degree moment) and clarify whether the connection is independent of prior SoS reductions or follows directly from them, as this bears on the method's foundational independence.
  2. [Tensor PCA] Tensor-PCA section: the 'sharp low-degree lower bound against subexponential-time algorithms' is presented as a highlight. The text should explicitly compare the obtained threshold (via the second-moment calculation) to the best known algorithmic upper bounds to substantiate the sharpness claim; without this comparison the load-bearing prediction for subexponential regimes remains incompletely verified.
minor comments (3)
  1. [Preliminaries] Notation for the low-degree likelihood ratio and its second moment is introduced early but reused with slight variations later; a single consolidated definition table or equation block would improve readability.
  2. [Applications] Several conjectural predictions for specific problems (e.g., planted clique, community detection) are listed; adding a short table summarizing the predicted thresholds versus known rigorous bounds would help readers track the method's reach.
  3. [References] A few citations to recent follow-up works that test the low-degree predictions empirically or rigorously are missing from the reference list.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and recommendation of minor revision. We address each major comment below and will make the suggested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [Introduction / spectral-methods section] The abstract and introduction claim a 'formal connection between spectral methods and the low-degree likelihood ratio' as a rigorous new result. The manuscript should state the precise theorem (including any equation defining the low-degree moment) and clarify whether the connection is independent of prior SoS reductions or follows directly from them, as this bears on the method's foundational independence.

    Authors: We agree that greater precision will improve clarity. The connection is derived directly from the definition of the low-degree likelihood ratio (without invoking prior SoS reductions) and is presented as an independent rigorous result. In the revision we will state the precise theorem explicitly, including the defining equation for the low-degree moment (the second moment of the degree-D truncated likelihood ratio), and add a sentence clarifying its independence from SoS techniques. revision: yes

  2. Referee: [Tensor PCA] Tensor-PCA section: the 'sharp low-degree lower bound against subexponential-time algorithms' is presented as a highlight. The text should explicitly compare the obtained threshold (via the second-moment calculation) to the best known algorithmic upper bounds to substantiate the sharpness claim; without this comparison the load-bearing prediction for subexponential regimes remains incompletely verified.

    Authors: We accept that an explicit side-by-side comparison will strengthen the claim. The low-degree threshold obtained from the second-moment calculation matches (up to logarithmic factors) the best known subexponential algorithmic upper bounds for tensor PCA. In the revision we will insert a short paragraph in the tensor-PCA section that directly compares the two, citing the relevant algorithmic results, thereby substantiating the sharpness statement for subexponential regimes. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper is a survey of the low-degree method, which it explicitly frames as a posit (the second moment of the low-degree likelihood ratio predicts computational hardness) rather than a derived theorem. It distinguishes rigorous results (e.g., formal spectral connection, sharp tensor PCA lower bound) from conjectural consequences and provides a self-contained introduction without relying on unverified self-citations or reductions of predictions to fitted inputs. No load-bearing step reduces by construction to its own inputs; the central claim is presented as conjectural with independent content.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that the second moment of the low-degree likelihood ratio predicts computational hardness; no free parameters or invented entities are identified from the abstract.

axioms (1)
  • domain assumption The second moment of the low-degree likelihood ratio gives insight into computational time required for hypothesis testing
    This is the core posit of the low-degree method as stated in the abstract.

pith-pipeline@v0.9.0 · 5733 in / 1255 out tokens · 39085 ms · 2026-05-24T15:06:37.685678+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 2 Pith papers

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

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

    math.ST 2026-03 accept novelty 8.0

    The minimax rate for estimating d-th order moment tensors is sqrt(p/n) wedge 1, while low-degree evidence shows detection of vanishing cumulants is hard for n much less than p to the d/2, creating a reverse detection-...

  2. High-Dimensional Statistics: Reflections on Progress and Open Problems

    math.ST 2026-05 unverdicted novelty 2.0

    A survey synthesizing representative advances, common themes, and open problems in high-dimensional statistics while pointing to key entry-point works.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · cited by 2 Pith papers · 13 internal anchors

  1. [1]

    Algorit hmic barriers from phase transi- tions

    [ACO08] Dimitris Achlioptas and Amin Coja-Oghlan. Algorit hmic barriers from phase transi- tions. In 2008 49th Annual IEEE Symposium on Foundations of Computer Sci ence, pages 793–802. IEEE,

    work page 2008

  2. [2]

    Homotopy Analysis for Tensor PCA

    [ADGM16] Anima Anandkumar, Yuan Deng, Rong Ge, and Hossein M obahi. Homotopy analysis for tensor PCA. arXiv preprint arXiv:1610.09322 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    High-dimensio nal analysis of semidefinite relaxations for sparse principal components

    [A W08] Arash A Amini and Martin J Wainwright. High-dimensio nal analysis of semidefinite relaxations for sparse principal components. In 2008 IEEE International Symposium on Information Theory , pages 2454–2458. IEEE,

    work page 2008

  4. [4]

    Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

    [BB19] Matthew Brennan and Guy Bresler. Optimal average-ca se reductions to sparse PCA: From weak assumptions to strong hardness. arXiv preprint arXiv:1902.07380 ,

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  5. [5]

    R educibility and compu- tational lower bounds for problems with planted sparse stru cture

    [BBH18] Matthew Brennan, Guy Bresler, and Wasim Huleihel. R educibility and compu- tational lower bounds for problems with planted sparse stru cture. arXiv preprint arXiv:1806.07508,

    work page arXiv

  6. [6]

    Algorithmic thresholds for tensor PCA

    [BGJ18] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagann ath. Algorithmic thresholds for tensor PCA. arXiv preprint arXiv:1808.00921 ,

    work page arXiv

  7. [7]

    Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

    [BGL16] Vijay Bhattiprolu, Venkatesan Guruswami, and Euiw oong Lee. Sum-of-squares certifi- cates for maxima of random tensors on the sphere. arXiv preprint arXiv:1605.00903 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  8. [8]

    Computational Hardness of Certifying Bounds on Constrained PCA Problems

    [BKW19] Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein. Computational hardness of certifying bounds on constrained PCA problems. arXiv preprint arXiv:1902.07324 ,

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  9. [9]

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

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

    work page 2015

  10. [10]

    Notes on computational-to-statistical gaps: predictions using statistical physics

    [BPW18] Afonso S Bandeira, Amelia Perry, and Alexander S Wei n. Notes on computational-to- statistical gaps: predictions using statistical physics. arXiv preprint arXiv:1803.11132,

    work page internal anchor Pith review Pith/arXiv arXiv

  11. [11]

    Computational Lower Bounds for Sparse PCA

    [BR13] Quentin Berthet and Philippe Rigollet. Computation al lower bounds for sparse PCA. arXiv preprint arXiv:1304.0828 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    Asymptotic Mutual Information for the Two-Groups Stochastic Block Model

    [DAM15] Yash Deshpande, Emmanuel Abbe, and Andrea Montanar i. Asymptotic mutual infor- mation for the two-groups stochastic block model. arXiv preprint arXiv:1507.08685 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  13. [13]

    Statistical query lower bounds for robust estimation of high-dimensional gaussian s and gaussian mixtures

    [DKS17] Ilias Diakonikolas, Daniel M Kane, and Alistair Ste wart. Statistical query lower bounds for robust estimation of high-dimensional gaussian s and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Sci ence (FOCS) , pages 73–84. IEEE,

    work page 2017

  14. [14]

    Estimation in t he spiked Wigner model: A short proof of the replica formula

    [EK18] Ahmed El Alaoui and Florent Krzakala. Estimation in t he spiked Wigner model: A short proof of the replica formula. In 2018 IEEE International Symposium on Information Theory (ISIT) , pages 1874–1878. IEEE,

    work page 2018

  15. [15]

    Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model

    [EKJ17] Ahmed El Alaoui, Florent Krzakala, and Michael I Jor dan. Finite size correc- tions and likelihood ratio fluctuations in the spiked Wigner model. arXiv preprint arXiv:1710.02903,

    work page internal anchor Pith review Pith/arXiv arXiv

  16. [16]

    Fundamental limits of detection in the spiked Wigner model

    [EKJ18] Ahmed El Alaoui, Florent Krzakala, and Michael I Jor dan. Fundamental limits of detection in the spiked Wigner model. arXiv preprint arXiv:1806.09588 ,

    work page arXiv

  17. [17]

    Sparse high-dimensi onal linear regression

    [GZ17] David Gamarnik and Ilias Zadik. Sparse high-dimensi onal linear regression. algorith- mic barriers and a local search algorithm. arXiv preprint arXiv:1711.04952 ,

    work page arXiv

  18. [18]

    The landscape of the p lanted clique problem: Dense subgraphs and the overlap gap property

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

    work page arXiv 1904

  19. [19]

    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 Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on , pages 720–731. IEEE,

    work page 2017

  20. [20]

    Bayesian estimation from few samples: community detection and related problems

    [HS17] Samuel B Hopkins and David Steurer. Bayesian estimat ion from few samples: com- munity detection and related problems. arXiv preprint arXiv:1710.00264 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  21. [21]

    Statistical thresholds for tensor pca

    33 [JLM18] Aukosh Jagannath, Patrick Lopatto, and Leo Miolane . Statistical thresholds for tensor pca. arXiv preprint arXiv:1812.03403 ,

    work page arXiv

  22. [22]

    Chi-squared Amplification: Identifying Hidden Hubs

    [KV16] Ravi Kannan and Santosh Vempala. Beyond spectral: Ti ght bounds for planted gaussians. arXiv preprint arXiv:1608.03643 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  23. [23]

    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

  24. [24]

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

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

    work page 2015

  25. [25]

    Phase transitions in sparse PCA

    [LKZ15b] Thibault Lesieur, Florent Krzakala, and Lenka Zde borov´ a. Phase transitions in sparse PCA. In 2015 IEEE International Symposium on Information Theory (ISIT) , pages 1635–1639. IEEE,

    work page 2015

  26. [26]

    Statistical and computational phase transitions in spiked tensor estimation

    [LML+17] Thibault Lesieur, L´ eo Miolane, Marc Lelarge, Florent K rzakala, and Lenka Zdeborov´ a. Statistical and computational phase transitions in spiked tensor estimation. In 2017 IEEE International Symposium on Information Theory (ISIT) , pages 511–515. IEEE,

    work page 2017

  27. [27]

    Phase transitions in spiked matrix estimation: information-theoretic analysis

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

    work page internal anchor Pith review Pith/arXiv arXiv

  28. [28]

    Planting trees in graphs, and finding them back

    [MST18] Laurent Massouli´ e, Ludovic Stephan, and Don Towsl ey. Planting trees in graphs, and finding them back. arXiv preprint arXiv:1811.01800 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  29. [29]

    Statistical limits of spiked tensor models

    [PWB16] Amelia Perry, Alexander S Wein, and Afonso S Bandeir a. Statistical limits of spiked tensor models. arXiv preprint arXiv:1612.07728 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  30. [30]

    High-dimensional estima- tion via sum-of-squares proofs

    [RSS18] Prasad Raghavendra, Tselil Schramm, and David Steu rer. High-dimensional estima- tion via sum-of-squares proofs. arXiv preprint arXiv:1807.11419 ,

    work page arXiv

  31. [31]

    Linear level Lasserre lower bou nds for certain k-CSPs

    [Sch08] Grant Schoenebeck. Linear level Lasserre lower bou nds for certain k-CSPs. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages 593–602. IEEE,

    work page 2008

  32. [32]

    Statistical and com- putational trade-offs in estimation of sparse principal comp onents

    [WBS16] Tengyao Wang, Quentin Berthet, and Richard J Samwor th. Statistical and com- putational trade-offs in estimation of sparse principal comp onents. The Annals of Statistics, 44(5):1896–1930,

    work page 1930

  33. [33]

    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 ,

    work page arXiv 1904