# Precise Error Rates for Computationally Efficient Testing

arXiv: https://arxiv.org/abs/2311.00289 · HTML: https://mlsanity.com/paper/2311.00289/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 67 references that are in the map.
- First posted on arXiv 1 Nov 2023.

## Builds on (most cited first, 27 of 27)

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013)
- [Fundamental limits of detection in the spiked Wigner model](https://mlsanity.com/paper/1806.09588/) (2018)
- [Phase Transitions in Sparse PCA](https://mlsanity.com/paper/1503.00338/) (2015)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [Optimal hypothesis testing for stochastic block models with growing degrees](https://mlsanity.com/paper/1705.05305/) (2017)
- [Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs](https://mlsanity.com/paper/2008.12237/) (2020)
- [Counterexamples to the Low-Degree Conjecture](https://mlsanity.com/paper/2004.08454/) (2020)
- [Computationally efficient sparse clustering](https://mlsanity.com/paper/2005.10817/) (2020)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [Hypothesis testing with low-degree polynomials in the Morris class of exponential families](https://mlsanity.com/paper/2011.03693/) (2020)
- [Is Planted Coloring Easier than Planted Clique?](https://mlsanity.com/paper/2303.00252/) (2023)
- [Is it easier to count communities than find them?](https://mlsanity.com/paper/2212.10872/) (2022)
- [Detection of Signal in the Spiked Rectangular Models](https://mlsanity.com/paper/2104.13517/) (2021)
- [Weak Detection in the Spiked Wigner Model with General Rank](https://mlsanity.com/paper/2001.05676/) (2020)
- [Weak detection in the spiked Wigner model](https://mlsanity.com/paper/1809.10827/) (2018)

## Built on by (most cited first, 4 of 4)

- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Low degree conjecture implies sharp computational thresholds in stochastic block model](https://mlsanity.com/paper/2502.15024/) (2025)
- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)

## Abstract (arXiv)

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 (conditional on a conjecture) 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.