Event Date
Speaker: Alex Wein, Associate Professor, Mathematics, UC Davis
Title: "Computational Complexity of Testing in the Spiked Wigner Model"
Abstract: We consider a canonical high-dimensional hypothesis testing problem: 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 "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 https://arxiv.org/abs/2311.00289 with Ankur Moitra which uses a version of the low-degree polynomial heuristic, as well as https://arxiv.org/abs/2609.36050 with Ansh Nagda which gives a stronger form of reduction-based hardness.
Website (external)