The Capacity of Adaptive Group Testing

Abstract

We define capacity for group testing problems and deduce bounds for the capacity of a variety of noisy models, based on the capacity of equivalent noisy communication channels. For noiseless adaptive group testing we prove an information-theoretic lower bound which tightens a bound of Chan et al. This can be combined with a performance analysis of a version of Hwang's adaptive group testing algorithm, in order to deduce the capacity of noiseless and erasure group testing models.

5 pages

References in corpus (3)

• Group testing algorithms: bounds and simulations
• Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
• Adaptive group testing as channel coding with feedback

Cited by in corpus (30)

• Group testing algorithms: bounds and simulations
• Performance of group testing algorithms with near-constant tests-per-item
• Individual testing is optimal for nonadaptive group testing in the linear regime
• The capacity of non-identical adaptive group testing
• The capacity of Bernoulli nonadaptive group testing
• Causality-Guided Adaptive Interventional Debugging
• Rates of adaptive group testing in the linear regime
• Almost Separable Matrices
• Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design
• Improved group testing rates with constant column weight designs
• Efficient Probabilistic Group Testing Based on Traitor Tracing
• Strong converses for group testing in the finite blocklength regime
• Improved bounds for noisy group testing with constant tests per item
• On the optimality of some group testing algorithms
• Lower Bounds on Active Learning for Graphical Model Selection
• A Fast Binary Splitting Approach to Non-Adaptive Group Testing
• On the All-Or-Nothing Behavior of Bernoulli Group Testing
• Near optimal sparsity-constrained group testing: improved bounds and algorithms
• Bayesian inference of infected patients in group testing with prevalence estimation
• Noisy group testing via spatial coupling
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Concomitant Group Testing
• Learning Erdős-Rényi Random Graphs via Edge Detecting Queries
• Small error algorithms for tropical group testing
• On Finding a Subset of Healthy Individuals from a Large Population
• Online neural connectivity estimation with ensemble stimulation
• Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices
• Improved Bounds and Algorithms for Sparsity-Constrained Group Testing
• Nearly Optimal Sparse Group Testing
• An Efficient Algorithm for Capacity-Approaching Noisy Adaptive Group Testing