Low-degree heuristic for computational detection

Let $\mathbb P$ and $\mathbb Q$ be probability measures for a high-dimensional hypothesis-testing problem based on $\mathsf Y\in\mathbb R^N$, with $N=N_n$ and parameters scaling with $n$. Let $\mathcal P_D$ be the polynomials on $\mathbb R^{N_n}$ of degree at most $D$, and define the low-degree advantage by

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

Strong detection means that the sum of type-I and type-II errors tends to zero, while weak detection means that this sum is bounded above by $1-\epsilon$ for some fixed $\epsilon>0$. Low-degree heuristic. For natural high-dimensional hypothesis-testing problems, (1) if $\mathsf{Adv}_{\leq D}(\mathbb P;\mathbb Q)=O(1)$ as $n\to\infty$, then for some constant $C$ no algorithm with running time $N^{D/(C\log N)}$ achieves strong detection; and (2) if $\mathsf{Adv}_{\leq D}(\mathbb P;\mathbb Q)=1+o(1)$ as $n\to\infty$, then for some constant $C$ no algorithm with that running time achieves weak detection. This heuristic is a central conditional principle relating low-degree testing bounds to computational hardness, and the source does not establish it as a theorem.