# Counterexamples to the Low-Degree Conjecture

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2020.

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

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Precise Error Rates for Computationally Efficient Testing](https://mlsanity.com/paper/2311.00289/) (2023)
- [Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression](https://mlsanity.com/paper/2402.14103/) (2024)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)

## Abstract (arXiv)

A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data. This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs via the low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins. However, our counterexample crucially exploits the specifics of the noise operator used in the conjecture, and we point out a simple way to modify the conjecture to rule out our counterexample. We also give an example illustrating that (even after the above modification), the symmetry assumption in the conjecture is necessary. These results do not undermine the low-degree framework for computational lower bounds, but rather aim to better understand what class of problems it is applicable to.