Precise error rates for computationally efficient testing

We consider one of the most basic high-dimensional testing problems: that of detecting the presence of a rank-1 "spike" in a random Gaussian (GOE) matrix. When the spike has structure such as sparsity, inherent statistical/computational tradeoffs are expected. I will discuss some precise results about the computational complexity, arguing that the so-called "linear spectral statistics" achieve the best possible tradeoff between type I and II errors among all polynomial-time algorithms, even though an exponential-time algorithm can do better. This is based on work with Ankur Moitra which uses a version of the low-degree polynomial heuristic, as well as forthcoming work with Ansh Nagda which gives a stronger form of reduction-based hardness.