Hopkins's low-degree conjecture for hypothesis testing

Consider asymptotic hypothesis-testing problems between probability measures $\mathbb P$ and $\mathbb Q$. For degree at most $D$, define the low-degree advantage by

$$\mathsf{Adv}_{\leq D}\left(\frac{\mathrm{d}\mathbb P}{\mathrm{d}\mathbb Q}\right):=\sup_{f\in\mathcal P_D}\frac{\mathbb E_{\mathbb P}[f]}{\sqrt{\mathbb E_{\mathbb Q}[f^2]}}.$$

Here $\mathcal P_D$ is the set of real polynomials of degree at most $D$, and $\mathrm{TV}$ denotes total variation distance. An algorithm achieves strong detection if the sum of its type-I and type-II errors tends to zero, and achieves weak detection if that sum is bounded above by $1-\epsilon$ for some fixed $\epsilon>0$. Hopkins's low-degree conjecture. For “natural” high-dimensional hypothesis-testing problems between $\mathbb P$ and $\mathbb Q$, the following statements hold: (1) if

$$\mathsf{Adv}_{\leq D}\left(\frac{\mathrm{d}\mathbb P'}{\mathrm{d}\mathbb Q'}\right)=O(1)$$

as $n\to\infty$ for some $\mathbb P',\mathbb Q'$ satisfying $\mathrm{TV}(\mathbb P,\mathbb P'),\mathrm{TV}(\mathbb Q,\mathbb Q')=o(1)$, then there exists a constant $C$ such that no algorithm with running time $n^{D/(\log n)^C}$ achieves strong detection between $\mathbb P$ and $\mathbb Q$; and (2) if

$$\mathsf{Adv}_{\leq D}\left(\frac{\mathrm{d}\mathbb P'}{\mathrm{d}\mathbb Q'}\right)=1+o(1)$$

under the same total-variation conditions, then there exists a constant $C$ such that no algorithm with running time $n^{D/(\log n)^C}$ achieves weak detection between $\mathbb P$ and $\mathbb Q$. The conjecture is a proposed bridge from low-degree polynomial analysis to computational lower bounds for natural high-dimensional testing problems. The source does not provide evidence resolving it in full generality.