Group Testing: An Information Theory Perspective

Abstract

The group testing problem concerns discovering a small number of defective items within a large population by performing tests on pools of items. A test is positive if the pool contains at least one defective, and negative if it contains no defectives. This is a sparse inference problem with a combinatorial flavour, with applications in medical testing, biology, telecommunications, information technology, data science, and more. In this monograph, we survey recent developments in the group testing problem from an information-theoretic perspective. We cover several related developments: efficient algorithms with practical storage and computation requirements, achievability bounds for optimal decoding methods, and algorithm-independent converse bounds. We assess the theoretical guarantees not only in terms of scaling laws, but also in terms of the constant factors, leading to the notion of the {\em rate} of group testing, indicating the amount of information learned per test. For the noiseless setting, we present a series of results leading to optimal rates, which in turn imply optimality and suboptimality results of various algorithms depending on the sparsity regime. We also survey analogous developments in noisy settings. In addition, we survey results concerning a number of variations on the standard group testing problem, including approximate recovery criteria, adaptive algorithms with a limited number of stages, sublinear-time algorithms, and settings with additional prior information, among others.

Second edition. Published in Foundations and Trends in Communications and Information Theory. The first edition can be found in arXiv v3

Cited by in corpus (34)

• Group testing as a strategy for the epidemiologic monitoring of COVID-19
• Positively Correlated Samples Save Pooled Testing Costs
• Contact Tracing Enhances the Efficiency of COVID-19 Group Testing
• Optimal group testing
• Rates of adaptive group testing in the linear regime
• Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design
• A Note on Double Pooling Tests
• Improved bounds for noisy group testing with constant tests per item
• On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
• Maximising the Benefits of an Acutely Limited Number of COVID-19 Tests
• Pooled testing to isolate infected individuals
• AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing
• Near optimal sparsity-constrained group testing: improved bounds and algorithms
• Group testing and local search: is there a computational-statistical gap?
• On the All-Or-Nothing Behavior of Bernoulli Group Testing
• A Fast Binary Splitting Approach to Non-Adaptive Group Testing
• Note on the offspring distribution for group testing in the linear regime
• Autosploit: A Fully Automated Framework for Evaluating the Exploitability of Security Vulnerabilities
• Learning Erdős-Rényi Random Graphs via Edge Detecting Queries
• Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
• Practical Near Neighbor Search via Group Testing
• Online neural connectivity estimation with ensemble stimulation
• Geometric group testing
• Improved Bounds and Algorithms for Sparsity-Constrained Group Testing
• Quantum algorithms for learning a hidden graph and beyond
• Improved non-adaptive algorithms for threshold group testing with a gap
• Efficient Detection Of Infected Individuals using Two Stage Testing
• Modelling the Utility of Group Testing for Public Health Surveillance
• Efficient Tuning-Free ${\ell }_1$-Regression of Nonnegative Compressible Signals
• Group Testing under Superspreading Dynamics
• Generalized Group Testing
• Scheduling Improves the Performance of Belief Propagation for Noisy Group Testing
• Decision Theoretic Cutoff and ROC Analysis for Bayesian Optimal Group Testing
• Near-Optimal Pool Testing under Urgency Constraints