IFML/ACT Seminar: 11/20/26 - Computational Complexity of Testing in the Spiked Wigner Model

Title: Computational Complexity of Testing in the Spiked Wigner Model

Abstract: The spiked Wigner model is a simple and canonical high-dimensional testing problem: detect the presence (or not) of a rank-1 "spike" in a large random Gaussian matrix. Despite its simplicity, the inherent statistical-computational tradeoffs are not fully understood, particularly when the spike has structure such as sparsity. I will ask a more precise question than prior work, seeking the optimal tradeoff between false-positive and false-negative rates. Conditional on an appropriate complexity-theoretic conjecture, we show that the "linear spectral statistics" achieve the best such tradeoff 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 an extension 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 that rigorously connects the strong and weak testing questions.

Bio: Alex Wein is an Associate Professor of Mathematics at the University of California, Davis. His research lies at the intersection of theoretical computer science, statistics, and machine learning, with a focus on the computational complexity of statistical inference. He received his PhD from MIT in 2018, advised by Ankur Moitra. Before joining UC Davis in 2022, he held postdoctoral positions at NYU, the Simons Institute at UC Berkeley, and Georgia Tech. He is a recipient of the Sloan Research Fellowship and NSF CAREER Award. (https://www.alex-wein.com/)

Zoom link: https://utexas.zoom.us/j/89110047398