From Weak to Strong Testing in Gaussian Models
Abstract
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 weak detection is entirely reduced to that of strong detection. The proof builds on ideas of Nagda-Raghavendra (2025) and Moitra-Wein (2025). The low-degree likelihood ratio (LDLR) plays a key role: any test that slightly beats the LDLR can be boosted to have an even higher success probability. This leads us to establish a computational analogue of the Neyman-Pearson lemma for a subclass of additive Gaussian models: for a given super-polynomial runtime, the best possible tradeoff between type I and II errors is either the one achieved by thresholding the LDLR, or the trivial tradeoff that results from strong detection.
Related
- Weak and strong Lefschetz properties for vertex cover Artinian algebras associated to graphs
- Weak-strong uniqueness for the Landau equation by a relative entropy method
- Weak and strong convergence of a general splitting approach for monotone multioperator inclusions
- Strong and Weak-Type Dispersive Estimates for the Energy-Critical Nonlinear Schrödinger Equation with an Inverse-Square Potential
- Testing Gaussian process with applications to super-resolution
BibTeX
@misc{nagda2026from,
title = {{From Weak to Strong Testing in Gaussian Models}},
author = {Ansh Nagda and Alexander S. Wein},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36050},
eprint = {2609.36050},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36050},
}
RIS
TY - UNPB
TI - From Weak to Strong Testing in Gaussian Models
AU - Ansh Nagda
AU - Alexander S. Wein
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.36050
UR - https://arxiv.org/abs/2609.36050
AB - 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 weak detection is entirely reduced to that of strong detection. The proof builds on ideas of Nagda-Raghavendra (2025) and Moitra-Wein (2025). The low-degree likelihood ratio (LDLR) plays a key role: any test that slightly beats the LDLR can be boosted to have an even higher success probability. This leads us to establish a computational analogue of the Neyman-Pearson lemma for a subclass of additive Gaussian models: for a given super-polynomial runtime, the best possible tradeoff between type I and II errors is either the one achieved by thresholding the LDLR, or the trivial tradeoff that results from strong detection.
ER -