REVIEW 13 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
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 13 Pith papers
-
Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths
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.
-
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.
-
The Polynomial-Time Low-Degree Conjecture is False
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.
-
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 to comment.