Alexander S. Wein

From Weak to Strong Testing in Gaussian Models

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"BBP"eigenvalue transition, it is expected that strong detection --- with both type I and II errors vanishing --- requires exponential time. As...