Rigorous Implications of the Low-Degree Heuristic

Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such results rely on the hypothesis that if the low-degree moments of the planted and null distributions are sufficiently close, then no efficient (noise-tolerant) algorithm should be able to distinguish between them. This hypothesis is appealing due to the simplicity of calculating the low-degree likelihood ratio (LDLR), a quantity that measures the similarity between low-degree moments. However, despite sustained interest in the area, it remains unclear whether low-degree indistinguishability actually rules out any interesting class of algorithms. In this work, we initiate the study and develop technical tools for translating LDLR upper bounds into rigorous lower bounds against concrete algorithms. As a consequence, for any permutation-invariant distribution P, we prove: 1.) If is over {0,1}n and is low-degree indistinguishable from U = ({0,1}n), then a noisy version of is statistically indistinguishable from U. 2.) If is over n and is low-degree indistinguishable from the standard Gaussian (0, 1)n, then no statistic based on symmetric polynomials of degree at most O(logn/loglogn) can distinguish between a noisy version of from (0, 1)n. 3.) If is over n× n and is low-degree indistinguishable from (0,1)n× n, then no constant-sized subgraph statistic can distinguish between a noisy version of and (0, 1)n× n. To obtain our results, we depart significantly from techniques typically used in the context of low-degree lower bounds. Instead, we show total variation closeness by carefully analyzing the Fourier transform of polynomials under the input distributions.