The Quasi-Polynomial Low-Degree Conjecture is False

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 nO(D) whenever 1) the null distribution is product on 0,1 ⁿ 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 ⁿ k that has a vanishing degree-n^1-O(ϵ) LDA with respect to the uniform distribution on 0,1 ⁿ k, yet the corresponding ϵ-noisy distinguishing problem can be solved in nO(log 1/(k-1)(n) ) 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 reals^n×n with a vanishing n^Ω(1)-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.