Rates of adaptive group testing in the linear regime

Abstract

We consider adaptive group testing in the linear regime, where the number of defective items scales linearly with the number of items. We analyse an algorithm based on generalized binary splitting. Provided fewer than half the items are defective, we achieve rates of over 0.9 bits per test for combinatorial zero-error testing, and over 0.95 bits per test for probabilistic small-error testing.

arXiv comment5 pages, 1 figure. This version corrects a typo in the optimal value of m at the end of Section II

References in corpus (7)

• Boolean Compressed Sensing and Noisy Group Testing
• Group testing algorithms: bounds and simulations
• Group Testing: An Information Theory Perspective
• The Capacity of Adaptive Group Testing
• 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 non-identical adaptive group testing

Cited by in corpus (3)

• Optimal adaptive group testing
• Noisy group testing via spatial coupling
• Modelling the Utility of Group Testing for Public Health Surveillance