Information-theoretic and algorithmic thresholds for group testing

Abstract

In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [Aldridge et al.\ 2016] the individuals are assigned to test groups randomly, with every individual joining an equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [Aldridge et al.\ 2014, Johnson et al.\ 2019].

References in corpus (14)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical physics of inference: Thresholds and algorithms
• Algorithmic barriers from phase transitions
• Group testing algorithms: bounds and simulations
• Information-theoretic thresholds from the cavity method
• The asymptotic $k$-SAT threshold
• Performance of group testing algorithms with near-constant tests-per-item
• Individual testing is optimal for nonadaptive group testing in the linear regime
• Group testing with Random Pools: Phase Transitions and Optimal Strategy
• The capacity of Bernoulli nonadaptive group testing
• Improved group testing rates with constant column weight designs
• Decoding from Pooled Data: Phase Transitions of Message Passing
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• On the optimality of some group testing algorithms

Cited by in corpus (6)

• Phase transitions in the mini-batch size for sparse and dense two-layer neural networks
• Improved bounds for noisy group testing with constant tests per item
• On the All-Or-Nothing Behavior of Bernoulli Group Testing
• Noisy group testing via spatial coupling
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Small error algorithms for tropical group testing