  We revisit the fundamental question of simple-versus-simple hypothesis
testing with an eye towards computational complexity, as the statistically
optimal likelihood ratio test is often computationally intractable in
high-dimensional settings. In the classical spiked Wigner model (with a general
i.i.d. spike prior) we show that an existing test based on linear spectral
statistics achieves the best possible tradeoff curve between type I and type II
error rates among all computationally efficient tests, even though there are
exponential-time tests that do better. This result is conditional on an
appropriate complexity-theoretic conjecture, namely a natural strengthening of
the well-established low-degree conjecture. Our result shows that the spectrum
is a sufficient statistic for computationally bounded tests (but not for all
tests).
  To our knowledge, our approach gives the first tool for reasoning about the
precise asymptotic testing error achievable with efficient computation. The
main ingredients required for our hardness result are a sharp bound on the norm
of the low-degree likelihood ratio along with (counterintuitively) a positive
result on achievability of testing. This strategy appears to be new even in the
setting of unbounded computation, in which case it gives an alternate way to
analyze the fundamental statistical limits of testing.
