Low-Degree Conjecture for hypothesis testing

Let $\P_N$ and $\Q_N$ be distributions on $\mathbb{R}^N$, and let $\chi^2(\P_N\|\Q_N):=\mathbb{E}_{\x\sim\Q_N}\left[\frac{d\P_N(\x)}{d\Q_N(\x)}\right]^2-1$. Write $\chi^2_{\leq D}(\P_N\|\Q_N)$ for its projection onto the space of degree-$D$ polynomials. Strong detection means success probability $1-o(1)$, while weak detection means success probability $\frac12+\epsilon$ for some constant $\epsilon>0$. Low-Degree Conjecture. If $\chi^2_{\leq D}(\P_N\|\Q_N)=O(1)$ for some $D=\omega(\log N)$, strong detection has no polynomial-time algorithm and requires runtime $\exp(\widetilde\Omega(D))$; if $\chi^2_{\leq D}(\P_N\|\Q_N)=o(1)$ for some $D=\omega(\log N)$, weak detection has no polynomial-time algorithm and requires runtime $\exp(\widetilde\Omega(D))$. The low-degree framework gives a common heuristic for computational lower bounds in problems such as sparse PCA, Planted Clique, and community detection, but the asserted connection to general polynomial-time algorithms remains conjectural.