# Statistical and Computational Phase Transitions in Group Testing

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 63 references that are in the map.
- First posted on arXiv 15 Jun 2022.

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

- [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)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [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)
- [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)
- [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)
- [All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation](https://mlsanity.com/paper/2006.07971/) (2020)
- [Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs](https://mlsanity.com/paper/2008.12237/) (2020)
- [Computationally efficient sparse clustering](https://mlsanity.com/paper/2005.10817/) (2020)
- [Computational Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1304.0828/) (2013)
- [On the All-Or-Nothing Behavior of Bernoulli Group Testing](https://mlsanity.com/paper/2001.10137/) (2020)
- [Information theoretic limits of learning a sparse rule](https://mlsanity.com/paper/2006.11313/) (2020)
- [Group testing and local search: is there a computational-statistical gap?](https://mlsanity.com/paper/2011.05258/) (2020)

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

- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024)
- [An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds](https://mlsanity.com/paper/2506.06259/) (2025)
- [Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes](https://mlsanity.com/paper/2303.00043/) (2023)
- [On a Near-Optimal & Efficient Algorithm for the Sparse Pooled Data Problem](https://mlsanity.com/paper/2312.14588/) (2023)
- [Low-degree phase transitions for detecting a planted clique in sublinear time](https://mlsanity.com/paper/2402.05451/) (2024)
- [Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise](https://mlsanity.com/paper/2510.08541/) (2025)

## Abstract (arXiv)

We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease within a population of size n, based on the outcomes of pooled tests which return positive whenever there is at least one infected individual in the tested group. We consider two different simple random procedures for assigning individuals to tests: the constant-column design and Bernoulli design. Our first set of results concerns the fundamental statistical limits. For the constant-column design, we give a new information-theoretic lower bound which implies that the proportion of correctly identifiable infected individuals undergoes a sharp "all-or-nothing" phase transition when the number of tests crosses a particular threshold. For the Bernoulli design, we determine the precise number of tests required to solve the associated detection problem (where the goal is to distinguish between a group testing instance and pure noise), improving both the upper and lower bounds of Truong, Aldridge, and Scarlett (2020). For both group testing models, we also study the power of computationally efficient (polynomial-time) inference procedures. We determine the precise number of tests required for the class of low-degree polynomial algorithms to solve the detection problem. This provides evidence for an inherent computational-statistical gap in both the detection and recovery problems at small sparsity levels. Notably, our evidence is contrary to that of Iliopoulos and Zadik (2021), who predicted the absence of a computational-statistical gap in the Bernoulli design.