The low-degree conjecture for high-dimensional testing

Let $t: \mathbb{N} \to \mathbb{N}$. Consider a “natural” high-dimensional testing problem specified by distributions $\mathbb{P}_N$ and $\mathbb{Q}_N$ on an observation space $\Omega_N$, and let $L_N$ denote the corresponding likelihood ratio, with $\|L_N^{\leq D(N)}\|$ its degree-$D(N)$ low-degree norm. Low-degree conjecture. If $\|L_N^{\leq D(N)}\|$ remains bounded as $N \to \infty$ whenever $D(N) \leq t(N)\,\operatorname{polylog}(N)$, then there is no sequence of functions $f_N: \Omega_N \to \{\textit{p},\textit{q}\}$, computable in time $N^{O(t(N))}$, that strongly distinguishes $\mathbb{P}_N$ and $\mathbb{Q}_N$; that is, no such sequence satisfies

$$\lim_{N \to \infty} \mathbb{Q}_N\left[f_N(Y)=\textit{q}\right]=\lim_{N \to \infty} \mathbb{P}_N\left[f_N(Y)=\textit{p}\right]=1.$$

The conjecture formalizes the observed connection between bounded low-degree likelihood-ratio norms and computational hardness, asserting that degree-$D$ polynomial methods capture the power of algorithms with runtime about $N^{O(D/\operatorname{polylog}(N))}$. It is explicitly presented as an informal conjecture for natural problems, so the scope of “natural” testing problems and the precise generality of the claim remain open.