The Capacity of Bernoulli Nonadaptive Group Testing

Matthew Aldridge

Research output: Contribution to journalArticlepeer-review

21 Citations (SciVal)
56 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)7142-7148
JournalIEEE Transactions on Information Theory
Issue number11
Early online date4 Sept 2017
Publication statusPublished - 1 Nov 2017


  • Capacity planning
  • Detection algorithms
  • Electronic mail
  • Entropy
  • Error probability
  • Testing

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'The Capacity of Bernoulli Nonadaptive Group Testing'. Together they form a unique fingerprint.

Cite this