REVIEW 11 cited by
Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
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.
Forward citations
Cited by 11 Pith papers
-
Learning $\mathsf{AC}^0$ Under Graphical Models
Quasipolynomial-time algorithms learn AC^0 circuits under graphical models with polynomial growth and strong spatial mixing by transferring low-degree approximations via new sampling methods.
-
Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors
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-...
-
Sharp Phase Transitions in Estimation with Low-Degree Polynomials
New techniques establish sharp lower bounds ruling out low-degree polynomial estimation at the BBP and Kesten-Stigum thresholds for planted submatrix, dense subgraph, spiked Wigner, and stochastic block models.
-
High-Dimensional Procrustes Matching via Tree Counts
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.
-
Efficiently Learning Drifting Halfspaces with Massart Noise
Efficient learner for drifting halfspaces with Massart noise achieves error η + Õ(Δ^{1/3}/γ), with lower-bound evidence that Δ^{1/3} scaling is necessary for low-degree polynomial tests.
-
Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
The paper establishes sharp low-degree thresholds for planted-vs-planted testing in planted submatrix and dense subgraph models that match known recovery thresholds down to the constant.
-
Linear Functional Testing with General Loadings in Sparse Regression: Separation Rates and Computational Barriers
Constructs an efficient mixed test for linear functional testing in sparse regression and proves information-theoretic and low-degree lower bounds on adaptive separation rates for general loadings, with computational ...
-
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
Online algorithms achieve multiplicative approximation r^{1/(r-1)} for maximum independent sets in dense r-uniform ER hypergraphs and (max γ_i)^{-1/(r-1)} for balanced sets in r-partite versions, with matching lower bounds.
-
Low-degree estimation thresholds in planted hypergraphs and tensor PCA
Establishes sharp low-degree estimation thresholds in planted hypergraphs and tensor PCA, resolving open hardness questions and yielding polynomial-time algorithms above thresholds.
-
On efficient robust regression with subquadratic samples
Near-linear time algorithm for robust regression under Gaussian covariates achieves O(sqrt(ε κ)) error with Õ(d/ε⁴) samples when ε κ ≲ 1, plus SQ and low-degree lower bounds.
-
Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
A model-independent framework converts mild low-degree testing advantages into conditional computational lower bounds for recovery tasks, recovering prior results for planted submatrix and SBM while providing new evid...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.