# Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2025.

## Built on by (most cited first, 19 of 19)

- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [Phase Transition for Stochastic Block Model with more than √n Communities](https://mlsanity.com/paper/2509.15822/) (2025)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)
- [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026)
- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)
- [Learning mathsfAC0 Under Graphical Models](https://mlsanity.com/paper/2604.06109/) (2026)
- [Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps](https://mlsanity.com/paper/2604.17410/) (2026)
- [Sharp Low-Degree Thresholds for Planted-vs-Planted Testing](https://mlsanity.com/paper/2606.05266/) (2026)
- [Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise](https://mlsanity.com/paper/2510.08541/) (2025)
- [Statistical-computational gap in multiple Gaussian graph alignment](https://mlsanity.com/paper/2512.00610/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)
- [Computationally sufficient statistics for Ising models](https://mlsanity.com/paper/2602.12449/) (2026)
- [Detection of local geometry in random graphs: information-theoretic and computational limits](https://mlsanity.com/paper/2603.24545/) (2026)
- [On efficient robust regression with subquadratic samples](https://mlsanity.com/paper/2605.18042/) (2026)
- [Efficiently Learning Drifting Halfspaces with Massart Noise](https://mlsanity.com/paper/2606.11149/) (2026)
- [High-Dimensional Procrustes Matching via Tree Counts](https://mlsanity.com/paper/2607.08538/) (2026)
- [On the Pseudo-Mixing of Kac's Walk](https://mlsanity.com/paper/2608.17374/) (2026)
- [Algorithms for adaptive and heteroskedastic linear regression at the computational threshold](https://mlsanity.com/paper/2608.18402/) (2026)

## Abstract (arXiv)

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.