Runtime lower-bound conjecture for sparse PCA in the hard regime

Let $W$ be a $\mathrm{GOE}(n)$ matrix, let $x\in\{0,1\}^n$ have exactly $k$ nonzero entries, and observe $Y=\frac{\lambda}{k}xx^\top+W$, with $1\ll k\ll n$. Exact recovery means outputting $x$ with probability tending to $1$ as $n\to\infty$.

Sparse PCA runtime conjecture. For any $\lambda$ in the hard regime

$$\sqrt{k/n}\ll\lambda\ll\min\{1,k/\sqrt n\},$$

any algorithm for exact recovery requires runtime

$$\exp\left(\tilde\Omega\left(\frac{k^2}{\lambda^2n}\right)\right).$$

This conjecture proposes a precise computational barrier in the regime where exact recovery is believed to be information-theoretically possible but no polynomial-time algorithm is known. Existing evidence includes reductions from planted clique, failure of approximate message passing, sum-of-squares lower bounds, and the overlap gap property, but those results do not establish this precise optimal-runtime expression.