The capacity of Bernoulli nonadaptive group testing
arXiv:1511.05201 · doi:10.1109/TIT.2017.2748564
Abstract
We consider nonadaptive group testing with Bernoulli tests, where each item is placed in each test independently with some fixed probability. We give a tight threshold on the maximum number of tests required to find the defective set under optimal Bernoulli testing. Achievability is given by a result of Scarlett and Cevher; here we give a converse bound showing that this result is best possible. Our new converse requires three parts: a typicality bound generalising the trivial counting bound, a converse on the COMP algorithm of Chan et al, and a bound on the SSS algorithm similar to that given by Aldridge, Baldassini, and Johnson. Our result has a number of important corollaries, in particular that, in denser cases, Bernoulli nonadaptive group testing is strictly worse than the best adaptive strategies.
arXiv comment7 pages, 1 figure
References in corpus (7)
- Boolean Compressed Sensing and Noisy Group Testing
- Group testing algorithms: bounds and simulations
- The Capacity of Adaptive Group Testing
- Non-adaptive Group Testing: Explicit bounds and novel algorithms
- Group testing with Random Pools: Phase Transitions and Optimal Strategy
- Almost Separable Matrices
- On the optimality of some group testing algorithms
Cited by in corpus (6)
- Performance of group testing algorithms with near-constant tests-per-item
- Information-theoretic and algorithmic thresholds for group testing
- Improved bounds for noisy group testing with constant tests per item
- Noisy group testing via spatial coupling
- Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
- Small error algorithms for tropical group testing