The low-degree runtime correspondence conjecture

Consider a testing problem in the asymptotic setting, with degree-$D$ polynomial tests used as a proxy for computationally efficient algorithms. Strong separation means

$$\sqrt{\max\{\operatorname{Var}_{\mathcal P}[f],\operatorname{Var}_{\mathcal Q}[f]\}}=o\left(\left|\mathbb E_{\mathcal P}[f]-\mathbb E_{\mathcal Q}[f]\right|\right),$$

while weak separation replaces $o(\cdot)$ by $O(\cdot)$. Low-degree conjecture, informal. If degree-$D$ polynomials fail to solve a testing problem in the sense of strong or weak separation for some $D=\omega(\log n)$, then no polynomial-time algorithm can solve the associated strong or weak detection task, respectively. More generally, failure of degree-$D$ polynomials implies that no algorithm with runtime $\exp(\widetilde\Omega(D))$ can solve the task, where $\widetilde\Omega(\cdot)$ hides a $\operatorname{polylog}(n)$ factor. This conjecture formalizes the use of low-degree polynomial tests as evidence for computational hardness, but its validity is not established in general.