Abstract
We revisit the fundamental question of simple-versus-simple hypothesistesting with an eye towards computational complexity, as the statisticallyoptimal likelihood ratio test is often computationally intractable inhigh-dimensional settings. In the classical spiked Wigner model with a generali.i.d. spike prior we show (conditional on a conjecture) that an existing testbased on linear spectral statistics achieves the best possible tradeoff curvebetween type I and type II error rates among all computationally efficienttests, even though there are exponential-time tests that do better. This resultis conditional on an appropriate complexity-theoretic conjecture, namely anatural strengthening of the well-established low-degree conjecture. Our resultshows that the spectrum is a sufficient statistic for computationally boundedtests (but not for all tests). To our knowledge, our approach gives the first tool for reasoning about theprecise asymptotic testing error achievable with efficient computation. Themain ingredients required for our hardness result are a sharp bound on the normof the low-degree likelihood ratio along with (counterintuitively) a positiveresult on achievability of testing. This strategy appears to be new even in thesetting of unbounded computation, in which case it gives an alternate way toanalyze the fundamental statistical limits of testing.