Subexponential hardness of strong detection below the BBP transition

Fix constants $\gamma > 0$, $\beta > -1$, and $\rho \in (0,1)$. Let $N=N(n)$ satisfy $n/N \to \gamma$ as $n \to \infty$. In the spiked Wishart model, under $\mathbb{Q}$ the observations are independent standard Gaussian vectors, while under $\mathbb{P}$ a centered Bernoulli spike $\bu \sim \mathcal{X}_\rho$ is drawn and the observations have covariance $\bm I_n+\beta\bu\bu^{\top}$ when this covariance is positive definite. Strong detection means distinguishing $\mathbb{P}$ from $\mathbb{Q}$ with both error probabilities $o(1)$. Spiked Wishart detection conjecture. For any constants $\gamma > 0$, $\beta > -1$, $\rho \in (0,1)$, and $\eta > 0$ such that $\beta^2 < \gamma$, there is no algorithm of runtime $\exp(O(n^{1-\eta}))$ that achieves strong detection in the spiked Wishart model with parameters $\gamma,\beta$ and spike prior $\mathcal{X}_\rho$. Below the BBP transition $\beta^2=\gamma$, polynomial-time spectral detection is unavailable, although strong detection can sometimes be achieved by brute force; the conjecture asserts subexponential-time impossibility in this regime.