Group testing: An information theory perspective

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, recent developments in the group testing problem are surveyed from an information-theoretic perspective. Several recent developments are covered: efficient algorithms with practical storage and computation requirements, achievability bounds for optimal decoding methods and algorithm-independent converse bounds. The theoretical guarantees are assessed 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. For the noiseless setting, a series of results are presented leading to optimal rates, which in turn imply optimality and suboptimality results of various algorithms depending on the sparsity regime. Analogous developements are also surveyed for noisy settings. In addition, results are surveyed concerning a number of variations on the standard group testing problem, including approximate recovery criteria, adaptive algorithms with a limited number of stages, sublinear-time algorithms and settings with additional prior information, among others.