The informal low degree conjecture for computational thresholds

Let $(\mathcal{X}_n,\mathcal{P})$ be a sequence of CLVMs, giving rise to sequences of measures $\mathbb{P}_n$ and $\mathbb{Q}_n$ on $\Omega^N$, where $N=N(n)$. Let $\mathsf{Adv}_{\leq D}(\mathcal{X}_n,\mathcal{P})$ denote the low-degree advantage, and let strong detection mean distinguishing the two measures with the corresponding strong-detection guarantee. For sufficiently nice priors and channels, Informal low degree conjecture. (i) If, for some $D=D(n)=\omega(\log n)$, $\mathsf{Adv}_{\leq D}(\mathcal{X}_n,\mathcal{P})=O(1)$ as $n\to\infty$, then no test computable in time polynomial in $n$ achieves strong detection between $\mathbb{P}_n$ and $\mathbb{Q}_n$. (ii) If, for some $D=D(n)=\omega(1)$, $\mathsf{Adv}_{\leq D}(\mathcal{X}_n,\mathcal{P})=O(1)$ as $n\to\infty$, then no test computable in time $\exp(D/\mathsf{polylog}(n))$ achieves strong detection between $\mathbb{P}_n$ and $\mathbb{Q}_n$. This conjecture formalizes the heuristic that low-degree polynomials capture the power of efficient algorithms at a given runtime budget. It is explicitly described as rough and imprecise, and known pathological counterexamples require additional clauses; nevertheless, it often gives hardness predictions consistent with other evidence.