The Capacity of Bernoulli Nonadaptive Group Testing

Matthew Aldridge

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)
41 Downloads (Pure)

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.

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

Keywords

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

ASJC Scopus subject areas

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

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

Cite this