Group testing: an information theory perspective

Matthew Aldridge, Oliver Johnson, Jonathan Scarlett

Research output: Contribution to journalReview article (Academic Journal)

2 Citations (Scopus)
23 Downloads (Pure)

Abstract

The group testing problem concerns discovering a small number of defective items within a large population by performing tests on pools of items. A test is positive if the pool contains at least one defective, and negative if it contains no defectives. This is a sparse inference problem with a combinatorial flavour, with applications in medical testing, biology, telecommunications, information technology, data science, and more. In this monograph, we survey recent developments in the group testing problem from an information-theoretic perspective. We cover several related developments: efficient algorithms with practical storage and computation requirements, achievability bounds for optimal decoding methods, and algorithm-independent converse bounds. We assess the theoretical guarantees not only in terms of scaling laws, but also in terms of the constant factors, leading to the notion of the rate of group testing, indicating the amount of information learned per test. Considering both noiseless and noisy settings, we identify several regimes where existing algorithms are provably optimal or near-optimal, as well as regimes where there remains greater potential for improvement. In addition, we survey results concerning a number of variations on the standard group testing problem, including partial recovery criteria, adaptive algorithms with a limited number of stages, constrained test designs, and sublineartime algorithms.
Original languageEnglish
Pages (from-to)196-392
Number of pages196
JournalFoundations and Trends in Communications and Information Theory
Volume15
Issue number3-4
DOIs
Publication statusPublished - 5 Dec 2019

Fingerprint Dive into the research topics of 'Group testing: an information theory perspective'. Together they form a unique fingerprint.

  • Cite this