mlsanityData to 7 Oct 2026

Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

arXiv 2009.06107 ↗First posted 13 Sep 2020cs.CC cs.DS cs.LGcited by 51

Not on the map. Why?

Abstract (arXiv)

Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach is to characterize the limits of restricted models of computation, which on the one hand yields strong computational lower bounds for powerful classes of algorithms and on the other hand helps guide the development of efficient algorithms. In this paper, we study two of the most popular restricted computational models, the statistical query framework and low-degree polynomials, in the context of high-dimensional hypothesis testing. Our main result is that under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. As corollaries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Sep 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 6; 2023: 13; 2024: 12; 2025: 11; 2026: 5.

51 papers.

Sort:

  1. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  2. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  3. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  4. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  5. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  6. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  7. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  8. 2024On the hardness of learning under symmetriescited by 13
  9. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11
  10. 2021Reconstruction on Trees and Low-Degree Polynomialscited by 10
  11. 2022Statistical and Computational Phase Transitions in Group Testingcited by 10
  12. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
38 more
  1. 2023Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecited by 9
  2. 2023Statistical-Computational Tradeoffs in Mixed Sparse Linear Regressioncited by 7
  3. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  4. 2025Feature learning from non-Gaussian inputs: the case of Independent Component Analysis in high dimensionscited by 7
  5. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  6. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  7. 2023Semidefinite programs simulate approximate message passing robustlycited by 6
  8. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  9. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  10. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 6
  11. 2023Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noisecited by 5
  12. 2022Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Modelscited by 4
  13. 2023SQ Lower Bounds for Learning Mixtures of Linear Classifierscited by 4
  14. 2024Computational-Statistical Gaps for Improper Learning in Sparse Linear Regressioncited by 4
  15. 2023SQ Lower Bounds for Random Sparse Planted Vector Problemcited by 3
  16. 2023Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networkscited by 3
  17. 2024Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testingcited by 3
  18. 2025Phase Transition for Stochastic Block Model with more than √n Communities (II)cited by 3
  19. 2023Sparse PCA Beyond Covariance Thresholdingcited by 2
  20. 2024Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contaminationcited by 2
  21. 2024Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensingcited by 2
  22. 2024Low coordinate degree algorithms II: Categorical signals and generalized stochastic block modelscited by 2
  23. 2025Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noisecited by 2
  24. 2025Low degree conjecture implies sharp computational thresholds in stochastic block modelcited by 2
  25. 2023A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Normcited by 1
  26. 2024A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimationcited by 1
  27. 2025An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Boundscited by 1
  28. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 1
  29. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  30. 2024Sparse Linear Regression when Noises and Covariates are Heavy-Tailed and Contaminated by Outlierscited by 0
  31. 2025A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomialscited by 0
  32. 2025Phase Transition for Stochastic Block Model with more than √n Communitiescited by 0
  33. 2025Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contaminationcited by 0
  34. 2025Statistical and computational challenges in rankingcited by 0
  35. 2026Low-degree Lower bounds for clustering in moderate dimensioncited by 0
  36. 2026Low-Degree Method Fails to Predict Robust Subspace Recoverycited by 0
  37. 2026High-Dimensional Gaussian Mean Estimation under Realizable Contaminationcited by 0
  38. 2026Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barrierscited by 0

50 most cited of 51 All 51 (JSON)