Optimal group testing
arXiv:1911.02287 · doi:10.1017/S096354832100002X
Abstract
In the group testing problem the aim is to identify a small set of infected individuals out of a population size , . We avail ourselves of a test procedure capable of testing groups of individuals, with the test returning a positive result iff at least one individual in the group is infected. The aim is to devise a test design with as few tests as possible so that the set of infected individuals can be identified correctly with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition $\minf$ for non-adaptive group testing, where all tests are conducted in parallel. Thus, with more than $\minf$ tests the infected individuals can be identified in polynomial time \whp, while learning the set of infected individuals is information-theoretically impossible with fewer tests. In addition, we develop an optimal adaptive scheme where the tests are conducted in two stages.
References in corpus (13)
- Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
- Statistical physics of inference: Thresholds and algorithms
- Group testing algorithms: bounds and simulations
- Group Testing: An Information Theory Perspective
- Evolution of scaling emergence in large-scale spatial epidemic spreading
- 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
- Decoding from Pooled Data: Phase Transitions of Message Passing
- Decoding from Pooled Data: Sharp Information-Theoretic Bounds
- Understanding Phase Transitions via Mutual Information and MMSE