Polynomial-time lower bound for regression risk

Fix $\pi\in\mathcal P_2(\mathbb R)$, $\delta\in(0,\infty)$, and $\sigma>0$. Consider sequences of dimensions, Gaussian design matrices, coefficient vectors, and noise vectors satisfying the HDA and RSN assumptions at $\pi,\delta,\sigma$. Polynomial-time regression lower-bound conjecture. No polynomial-time algorithm achieves asymptotic risk smaller than $\delta\tau_{\mathsf{reg,alg}*}^2-\sigma^2$. This conjecture asserts a computational barrier matching the risk attained asymptotically by Bayes-AMP; the paper states that no polynomial-time algorithm achieving a lower risk is known.