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, which postulates that a vanishing degree-D LDA implies the absence of any noise-tolerant distinguishing algorithm with runtime n^widetildeO(D) whenever 1) the null distribution is product on 0,1^binomnk, and 2) the planted distribution is permutation invariant, that is, invariant under any relabeling [n] rightarrow [n]. In this paper, we disprove this conjecture. Specifically, we show that for any fixed varepsilon>0 and k≥ 2, there is a permutation-invariant planted distribution on 0,1^binomnk that has a vanishing degree-n1-O(varepsilon) LDA with respect to the uniform distribution on 0,1^binomnk, yet the corresponding varepsilon-noisy distinguishing problem can be solved in n^O(log1/(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 ℝn × n with a vanishing nOmega(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.