Skip to content

Group testing: an information theory perspective

Research output: Contribution to journalReview article

Original languageEnglish
Pages (from-to)196-392
Number of pages196
JournalFoundations and Trends in Communications and Information Theory
Volume15
Issue number3-4
DOIs
DateAccepted/In press - 25 Sep 2019
DatePublished (current) - 5 Dec 2019

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.

Documents

Documents

  • Full-text PDF (accepted author manuscript)

    Rights statement: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via Now Publishers Inc at https://www.nowpublishers.com/article/Details/CIT-099. Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 1 MB, PDF document

    Embargo ends: 5/05/20

    Request copy

Links

DOI

View research connections

Related faculties, schools or groups