{"id":"arxiv/2609.36050","url":"https://arxiv.org/abs/2609.36050","tags":["math.ST","cs.CC"],"score":0,"title":"From Weak to Strong Testing in Gaussian Models","domain":"math.ST","source":"arxiv","authors":["Ansh Nagda","Alexander S. Wein"],"reviews":0,"subject":"math.ST","summary":"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. Assuming this as a conjecture, we determine the limits of polynomial-time weak detection, exactly characterizing the possible tradeoffs between type I and II errors. Specifically, the optimal tradeoff is achieved by a particular linear spectral statistic. Thus, the question of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}