# Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

arXiv: https://arxiv.org/abs/2009.06107 · HTML: https://mlsanity.com/paper/2009.06107/

## Key facts

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

## Built on by (most cited first, 30 of 51)

- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [Statistical and Computational Phase Transitions in Group Testing](https://mlsanity.com/paper/2206.07640/) (2022)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2306.16352/) (2023)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Feature learning from non-Gaussian inputs: the case of Independent Component Analysis in high dimensions](https://mlsanity.com/paper/2503.23896/) (2025)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models](https://mlsanity.com/paper/2206.04589/) (2022)
- [SQ Lower Bounds for Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/2310.11876/) (2023)
- [Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression](https://mlsanity.com/paper/2402.14103/) (2024)
- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [SQ Lower Bounds for Random Sparse Planted Vector Problem](https://mlsanity.com/paper/2301.11124/) (2023)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)

## 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.