Performance of Group Testing Algorithms With Near-Constant Tests-per-Item

Oliver Johnson, Matthew P Aldridge, Jonathan Scarlett

Research output: Contribution to journalArticle (Academic Journal)peer-review

39 Citations (Scopus)
325 Downloads (Pure)


We consider the nonadaptive group testing with N items, of which K = Θ (N θ) are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for θ > 0.43 and the best proven performance with a practical decoding algorithm for all θ ∞ (0,1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when θ > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.

Original languageEnglish
Article number8423683
Pages (from-to)707-723
Number of pages17
JournalIEEE Transactions on Information Theory
Issue number2
Early online date31 Jul 2018
Publication statusPublished - 1 Feb 2019


  • Algorithm design and analysis
  • group testing
  • measurement design
  • performance bounds
  • sparse models


Dive into the research topics of 'Performance of Group Testing Algorithms With Near-Constant Tests-per-Item'. Together they form a unique fingerprint.

Cite this