The capacity of Bernoulli nonadaptive group testing

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.

7 pages, 1 figure

References in corpus (2)

• Group testing with Random Pools: Phase Transitions and Optimal Strategy
• 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