Group testing: an information theory perspective
From MaRDI portal
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. Considering both noiseless and noisy settings, we identify several regimes where existing algorithms are provably optimal or near-optimal, as well as regimes where there remains greater potential for improvement. In addition, we survey results concerning a number of variations on the standard group testing problem, including partial recovery criteria, adaptive algorithms with a limited number of stages, constrained test designs, and sublinear-time algorithms.
Recommendations
Cited in
(41)- A recovery algorithm and pooling designs for one-stage noisy group testing under the probabilistic framework
- Mathematical formation and analysis of COVID-19 pool tests strategies
- Generalized framework for group testing: queries, feedbacks and adversaries
- Random and quasi-random designs in group testing
- Real-valued group testing for quantitative molecular assays
- A survey on nonadaptive group testing algorithms through the angle of decoding
- Group Testing for Binary Markov Sources: Data-Driven Group Queries for Cooperative Sensor Networks
- Born again group testing: Multiaccess communications
- A Fundamental Monotonicity in Group Testing
- Phase transitions in group testing
- Group testing: revisiting the ideas
- Pooled Testing and Its Applications in the COVID-19 Pandemic
- Information-theoretic and algorithmic thresholds for group testing
- A tractable non-adaptative group testing method for non-binary measurements
- Algorithms and Data Structures
- Improved Combinatorial Group Testing Algorithms for Real‐World Problem Sizes
- Optimal group testing
- scientific article; zbMATH DE number 7758315 (Why is no real title available?)
- An interpretable classification method for predicting drug resistance in M. tuberculosis
- Flexible, efficient, and accurate tests for epidemics
- A survey of cover-free families: constructions, applications, and generalizations
- Optimal Dorfman group testing for symmetric distributions
- Is group testing ready for prime-time in disease identification?
- Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
- An efficient algorithm for group testing with runlength constraints
- Dynamic batching of online arrivals to leverage economies of scale
- Noisy group testing via spatial coupling
- On the optimal nested ordered algorithm
- Constructions of optimal sparse r-disjunct matrices via packings
- A negative binomial approximation in group testing
- Twenty questions with random error
- Pooled testing in the presence of congestion
- Lower bounds for graph reconstruction with maximal independent set queries
- A tight lower bound on non-adaptive group testing estimation
- On a near-optimal and efficient algorithm for the sparse pooled data problem
- Inference and mutual information on random factor graphs
- On the MCMC performance in Bernoulli group testing and the random max-set cover problem
- A new adaptive algorithm for competitive group testing
- Cover-free families on hypergraphs and combinatorial group testing
- An optimized Franz-Parisi criterion and its equivalence with SQ lower bounds
- Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing
This page was built for publication: Group testing: an information theory perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5213209)
