From Weak to Strong Testing in Gaussian Models

Ansh Nagda, Alexander S. Wein

We study the computational complexity of hypothesis testing in the spiked Wigner model, a prototypical model for detecting low-rank structure in a large random matrix. Below the "B…