The Quasi-Polynomial Low-Degree Conjecture is False

Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, Pravesh K. Kothari

This paper, recently released by researchers from ETH Zurich, Carnegie Mellon, and Princeton, delivers a major blow to a popular pillar of theoretical computer science: the Low-Degree Conjecture. For years, this conjecture has served as a "litmus test" for determining whether a statistical problem is computationally hard. By providing two clever counter-examples, the authors show that this heuristic—while often useful—is fundamentally incomplete.

TL;DR

The "Low-Degree Conjecture," a widely used heuristic for predicting the computational hardness of average-case statistical problems, is false. The authors demonstrate that certain "algebraic" structures (like error-correcting codes) allow efficient, noise-tolerant algorithms to succeed even when low-degree polynomials—the standard yardstick for hardness—fail to detect any signal.

What Problem Does This Paper Address?

In the world of average-case complexity, we often want to know: "Is this problem actually hard, or have we just not found the right algorithm yet?" Unlike worst-case complexity (where we have P vs. NP), average-case complexity lacks a unified theory.

To fill this gap, researchers have relied on the Low-Degree Conjecture (LDC). The LDC posits that for a broad class of problems (specifically those with high symmetry and noise tolerance), if a low-degree polynomial cannot distinguish between "random noise" (the null distribution) and "noise with a hidden signal" (the planted distribution), then no efficient algorithm can.

This conjecture has been used to justify the security of cryptographic protocols and to define the "information-computation gap" in statistics. This paper asks a simple but dangerous question: Is the Low-Degree Conjecture actually true?

Methods

The authors disprove the conjecture by constructing two specific "counter-examples"—scenarios where the low-degree advantage is zero (suggesting the problem is hard), but an efficient algorithm exists anyway.

  1. The Coding Theory Approach: The authors use Reed-Solomon codes and the problem of Noisy Polynomial Interpolation. They hide the evaluations of a secret polynomial within a high-dimensional tensor. They prove that while the low-degree moments of this distribution look identical to pure noise, a sophisticated "list-decoding" algorithm (specifically the Guruswami-Sudan algorithm) can recover the signal in quasi-polynomial time.
  2. The Spectral Approach: They construct a matrix-based problem where the signal is hidden in the top eigenvalue. They show that while polynomials of degree $O(\log n)$ are "blind" to this signal, a simple spectral algorithm (computing the largest eigenvalue) can distinguish the distributions in polynomial time.

Datasets

As a theoretical computer science paper, no real-world datasets were used. Instead, the authors defined and analyzed mathematical distributions:

  • Null Distributions ($Q_n$): Typically uniform distributions over Boolean tensors or symmetric matrices (pure noise).
  • Planted Distributions ($P_n$): Distributions containing a hidden structure (a "signal") that is invariant under permutations (to satisfy the conjecture's requirements).

Key Insights and Ideas

  • Symmetry is not a Shield: The LDC was thought to hold as long as the problem had enough "symmetry" (permutation invariance). This paper shows that even with perfect symmetry, algebraic structures like Reed-Solomon codes can bypass the low-degree barrier.
  • The Power of List-Decoding: A key "aha moment" is the realization that list-decoding is more powerful than what simple low-degree polynomials can represent. List-decoding allows an algorithm to produce a small set of candidates and then verify them, a process that doesn't map neatly onto the "low-degree advantage" framework.
  • Spectral Methods vs. Polynomials: There is a common folklore belief that spectral methods are "captured" by low-degree polynomials (specifically, that the top eigenvalue is just a very high-degree polynomial). The authors provide a concrete case where the top eigenvalue works as a distinguisher while low-degree polynomials fail, proving this intuition wrong in certain regimes.

Key Results

  • Disproof of the Main Conjecture: The authors show that for any fixed $\epsilon > 0$, there is a distribution where the low-degree advantage vanishes for degrees up to $n^{1-O(\epsilon)}$, yet a noise-tolerant distinguisher exists with a runtime of $n^{O(\log n)}$ (quasi-polynomial).
  • Polynomial-Time Counter-example: In a slightly different setting (rectangular inputs), they show that the gap is even more dramatic: the low-degree advantage vanishes, but a polynomial-time algorithm succeeds.
  • Spectral Success: They prove that for certain rotational-invariant distributions, the top eigenvalue serves as an efficient distinguisher even when the $n^{\Omega(1)}$-degree advantage is negligible.

Limitations and Future Work

The primary counter-example for the Boolean version of the conjecture results in a quasi-polynomial time algorithm ($n^{\log n}$), not a strictly polynomial one. While this is enough to technically disprove the conjecture (which predicted no such algorithm should exist), it leaves open the question of whether a "Polynomial Low-Degree Conjecture" might still hold in some form.

The authors conclude that while the low-degree heuristic is a powerful tool, it cannot be treated as a law of nature. Future work will likely focus on developing a more refined theory of average-case complexity that accounts for "algebraic" algorithms like list-decoding and lattice-based methods, which the low-degree framework currently ignores.

Summary updated

Abstract

There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) — a quantitative estimate of the closeness of low-degree moments — between a null distribution and a related planted distribution. Such hardness results are now ubiquitous not only for foundational average-case problems but also central questions in statistics and cryptography. This line of work is supported by the low-degree conjecture of Hopkins [1], which postulates that a vanishing degree-D LDA implies the absence of any noise-tolerant distinguishing algorithm with runtime ${n^{\tilde {\mathcal{O}}(D)}}$ whenever 1) the null distribution is product on ${\{ 0,1\} ^{\binom{n}{k}}}$, and 2) the planted distribution is permutation invariant, that is, invariant under any relabeling [n] → [n].In this paper, we disprove this conjecture. Specifically, we show that for any fixed ε > 0 and k ⩾ 2, there is a permutation-invariant planted distribution on ${\{ 0,1\} ^{\binom{n}{k}}}$ that has a vanishing degree-n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1−O(ε)</sup> LDA with respect to the uniform distribution on ${\{ 0,1\} ^{\binom{n}{k}}}$, yet the corresponding ε-noisy distinguishing problem can be solved in ${n^{O\left( {{{\log }^{1/(k - 1)}}(n)} \right)}}$ time. Our construction relies on algorithms for list-decoding for noisy polynomial interpolation in the high-error regime.We also give another construction of a pair of planted and (non-product) null distributions on ℝ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n×n</sup> with a vanishing n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Ω(1)</sup>-degree LDA while the largest eigenvalue serves as an efficient noise-tolerant distinguisher.Our results suggest that while a vanishing LDA may still be interpreted as evidence of hardness, developing a theory of average-case complexity based on such heuristics requires a more careful approach.
BibTeX
@misc{buhai2025quasi,
  author = {Rares-Darius Buhai and Jun-Ting Hsieh and Aayush Jain and Pravesh K. Kothari},
  title = {{The Quasi-Polynomial Low-Degree Conjecture is False}},
  year = {2025},
  eprint = {2505.17360},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.17360},
}
Figure