Group Testing: An Information Theory Perspective

Matthew Aldridge; Oliver Johnson; Jonathan Scarlett

Source-linked AI summary

Group Testing: An Information Theory Perspective

Matthew Aldridge, Oliver Johnson, Jonathan Scarlett

arXiv:1902.06002v4Feb 15, 2019cs.ITcs.DMmath.PRmath.ST

TL;DR

Group testing seeks to identify a small defective set using pooled binary tests while controlling the number of tests and error probability. This monograph surveys algorithms, information-theoretic bounds, rates, and extensions across noiseless and noisy settings. Its results characterize optimal rates and algorithm performance across sparsity regimes, alongside practical and theoretical trade-offs.

Problem
The problem is to discover a small number of defective items among many using pooled tests, while keeping tests and error probability small.
Method
The monograph surveys efficient algorithms, achievability and converse bounds, and rate-based analyses across noiseless, noisy, and extended group-testing models.
Results
Adaptive group testing has capacity C0 = C = 1 in sparse regimes, while surveyed noiseless results characterize optimal rates and practical decoding performance across sparsity regimes.
Takeaways & Limitations
The survey provides a unified information-theoretic view connecting test efficiency, algorithm design, decoding complexity, and sparsity-dependent optimality.
Takeaways & Limitations
The monograph focuses on theory and algorithms rather than applications, with Covid-19 testing discussed only selectively.

Abstract

from arXiv · show

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 {\em rate} of group testing, indicating the amount of information learned per test. For the noiseless setting, we present a series of results leading to optimal rates, which in turn imply optimality and suboptimality results of various algorithms depending on the sparsity regime. We also survey analogous developments in noisy settings. In addition, we survey results 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.

Preface to the second edition

The second edition adds new developments across noiseless and noisy group testing, algorithms, sparsity regimes, computational aspects, and non-binary models. It remains primarily theory- and algorithm-focused, while retaining open problems and limited application discussion.

New developments: New material covers optimal noiseless rates, polynomial-time decoding, improved noisy-testing results, sublinear-time algorithms, and linear-sparsity regimes.The edition also adds all-or-nothing thresholds, community-aware testing, computational aspects, and non-binary outcome models.
Scope: The monograph remains focused on theory and algorithms rather than applications, with Covid-19 testing discussed but not treated as a primary focus.For deeper pandemic-focused coverage, the authors direct readers to a separate survey.
Open problems: The concluding chapter updates previously posed open problems and introduces new ones after discussing problems that have been fully or partially solved.

Introduction to Group Testing

Group testing pools items to identify defectives using positive-or-negative outcomes, with the required tests depending on modeling and recovery choices. The survey emphasizes distinctions among noise, adaptivity, priors, and recovery criteria.

Basic idea: Pooling samples can reduce testing when defectives are rare, because a negative pooled test clears every included item while a positive test signals at least one defective.The idealized noiseless model treats dilution and other practical errors separately.
Inference problem: The central problem is to discover k defectives among n items while minimizing tests and maintaining a small error probability.
Testing modes: Nonadaptive tests are designed in advance, whereas adaptive tests can depend sequentially on previous outcomes; the survey mainly studies nonadaptive testing.
Design and decoding: Design chooses item pools, while decoding infers defectives from the test design and outcomes, ideally with computational efficiency.
Model distinctions: Results vary with noiseless versus noisy outcomes, binary versus nonbinary measurements, defective-set priors, known versus unknown k, and exact versus approximate recovery.

1.2 About this survey

This survey focuses on nonadaptive group testing with small nonzero error probability, especially sparse regimes, and evaluates both scaling and precise information-theoretic rates. It combines algorithms, limits, proofs, and extensions.

Survey focus: The survey differs from earlier works by emphasizing nonadaptive small-error testing rather than adaptive or zero-error settings.
Sparsity regimes: It concentrates on the sparse regime k = Θ(n^α), while also considering very sparse and linear regimes and the challenges associated with changing sparsity.
Information-theoretic perspective: Beyond order-optimality, the survey quantifies constant factors through the rate of group testing, interpreted as information learned per test.
Coverage: The chapters cover noiseless and noisy algorithms, information-theoretic limits, approximate recovery, limited-stage adaptivity, sublinear decoding, priors, constructions, constraints, and general models.
Presentation: Key results receive full proofs or proof sketches, while less central results are presented with references instead of proofs.

1.4 Counting bound and rate

The counting bound links the number of possible defective sets to a universal information limit, motivating rate as information learned per test. In sparse regimes, adaptive capacity is one, zero-error nonadaptive capacity is zero, and small-error nonadaptive capacity depends on sparsity.

Counting bound: The counting argument gives a universal capacity upper bound of C ≤ 1 and a strong converse: error probability tends to 1 below the corresponding test threshold.
Rate: The rate is defined as the entropy of the defective set divided by the number of tests, measuring average information learned per test.
Scaling: In the sparse regime, positive rate requires T = O(k log n) tests, whereas linear sparsity has different binomial-coefficient behavior.
Zero-error nonadaptive testing: Zero-error nonadaptive testing has capacity C0 = 0 for all α ∈ (0, 1).
Small-error nonadaptive testing: Small-error nonadaptive capacity equals 1 for α ∈ [0, 0.409] and then decreases from 1 to 0 as α increases toward 1.Near-constant tests-per-item designs attain the stated capacity across the full range, while Bernoulli designs attain it for α < 1/3.

1.5 A brief review of noiseless adaptive group testing

Noiseless adaptive group testing evolved from partition-based procedures to recursive binary splitting, which uses test outcomes to narrow the search for defectives.

Dorfman’s strategy partitions items into pools, individually testing items from positive pools while clearing negative pools.Later variants improve this two-stage procedure by testing positive pools individually until finding a defective and then retesting the remainder together.
Binary splitting recursively tests subsets of a candidate set to locate a defective or certify that the set contains none.A negative half-test still identifies the complementary half as containing a defective when the original set was known to be positive.
Halving the candidate set at each step means binary splitting finds a defective in at most ⌈log2 |A|⌉ adaptive tests.The set size can be rounded in either direction when forming the tested half.

1.5. A REVIEW OF NOISELESS ADAPTIVE GROUP TESTING

Repeated binary splitting gives effective adaptive recovery, while generalized splitting achieves the optimal sparse-regime rate; the advantage disappears for sufficiently dense instances.

k log2 n + O(k) adaptive tests suffice to find all k defectives even when k is unknown, yielding rate 1 −α for k = Θ(n^α).The procedure repeatedly searches the remaining items and stops after confirming that no defectives remain.
k log2(n/k)+O(k) adaptive tests raise the sparse-regime rate to 1 for every α ∈[0, 1).Generalized binary splitting exploits the fact that early tests are usually positive when many defectives remain.
Algorithm 1.2 divides the items into k roughly equal subsets and applies binary splitting to each subset.Each subset contains an average of one defective, enabling the total k log2(n/k)+O(k) bound.
Allemann reduced the implied constant in the O(k) term to 0.255k plus lower order terms.The leading test complexity remains k log2(n/k).
When k is sufficiently dense, adaptive testing may offer no advantage over individual testing; this is proved for k ≥0.369n under adaptive zero-error combinatorial testing.The survey focuses instead on the sparse regime k = Θ(n^α) with α ∈[0, 1).

1.6 A brief review of zero-error nonadaptive group testing

Zero-error nonadaptive testing requires test matrices that distinguish all admissible defective sets, but their test complexity yields capacity zero in the sparse regime.

A k-separable matrix gives distinct outcomes for every defective set of size k and is necessary for zero-error recovery.The corresponding ¯k-separable property handles all defective sets of size at most k.
A k-disjunct matrix prevents any nondefective item from appearing only in positive tests, enabling direct identification of defectives.Items appearing in negative tests are nondefective, while items appearing solely in positive tests are defective.
A 2k-separable matrix can be converted into a k-disjunct matrix by adding at most one row.This makes disjunctness bounds useful for separability results.
For k = Θ(n^α) with α > 1/2, the optimal zero-error disjunct-matrix design uses T = n individual tests.The identity matrix achieves the lower bound T ≥n in this regime.
For α < 1/2, disjunctness has lower bound Ω(k2) and constructions with T ≤O(k2 log n), while zero-error nonadaptive capacity is C0 = 0 for all α ∈(0, 1).Allowing a vanishing but nonzero error probability instead permits nonzero rates and rate 1 for α ∈[0, 0.409].

1.7 Applications of group testing

Group testing supports medical, biological, and other applications, especially when defectives are rare and tests can be run nonadaptively or in parallel.

Nonadaptive designs are useful when adaptive testing is impractical or when many tests should run in parallel.This motivates the survey’s attention to nonadaptive algorithms across applications.
Dorfman’s method was widely used for Covid-19 testing because it is simple, requires two stages, and is effective at roughly 2%–25% prevalence.Its practical use was limited as rapid, inexpensive at-home tests became more important than pooled PCR testing.
In biology, group testing reduces tests for rare genetic conditions and supports applications including drug screening, catalyst discovery, and protein-interaction experiments.Nonadaptive methods are typical in DNA testing and some biological settings.
Group testing can estimate the proportion of defective items when identifying individuals is unnecessary or confidentiality is important.Examples include estimating disease prevalence in insects and populations while preserving individual privacy.

Commmunication and signal processing

Group testing extends naturally to communications, networking, computing, and machine learning by treating sparse active, faulty, modified, or high-demand entities as defectives. These applications also motivate constraints such as connected test paths and noisy observations.

Communications: Communications applications model active users or occupied frequency bands as defectives, supporting adaptive and nonadaptive transmission or spectrum-scanning protocols.Multiple-access, CDMA, wireless-sensor, and cognitive-radio systems use group-testing-based designs to identify active users or occupied bands.
Networking: Network tomography treats network edges as items and end-to-end packet tests as pools, enabling fault detection from successful or failed transmissions.When tests must follow connected paths in the network, arbitrary pooling is unavailable and graph-constrained group testing becomes necessary.
Computing: Computing applications use group testing for data compression, file comparison, denial-of-service detection, database hot-item identification, and heavy-hitter discovery.These formulations map modified files, high-traffic users, or frequently accessed items to defectives and hashes, servers, or traffic measurements to tests.
Computing: Bloom-filter design is essentially a group testing problem involving the choice of hash-function count L and array size T.For suitable L, its analysis is nearly identical to COMP with a near-constant tests-per-item design, and it is connected to coding over an OR multiple-access channel.
Machine learning: Machine-learning uses include classification with many labels, near-neighbor search, pooled-image neural-network detection, and interpretable rule learning.These approaches represent labels, neighbors, images, or features through pooled or grouped tests to identify relevant positives.

Appendix: Comparison of combinatorial and i.i.d. priors

The monograph compares combinatorial and i.i.d. defective-set priors, showing that recovery and rate results transfer between them under sparse asymptotics, while also relating practical algorithms to information-theoretic limits. It reports optimal-rate results for several decoders and designs, alongside computational limitations for SSS.

Prior comparison: Theorem 1.7 transfers vanishing-error recovery and achievable rates from the combinatorial prior to the i.i.d. prior when k0 →∞ and k0 = o(n).The transfer applies when combinatorial recovery holds for k = k0(1 + o(1)).
Prior comparison: Theorem 1.8 transfers impossibility in the opposite direction with arbitrarily small ϵ, scaling both the average defective count and rate by 1 + ϵ.If rate R0 is impossible under the combinatorial prior at k = k0, it is also impossible under the i.i.d. prior at q = k0(1 + ϵ)/n for rate R0(1 + ϵ).
Prior comparison: For k = Θ(n^α), known achievability and converse rates depend on α rather than the implied constant in Θ(·), making the scaling adjustment asymptotically negligible.The stated results concern α ∈ (0, 1) and arbitrarily small ϵ.
Rates and algorithms: For α > 1/2, SSS, DD, SCOMP, and linear programming achieve rate 2 under optimized Bernoulli or constant tests-per-item designs.The near-constant design requires T ≥ (1 + η)(1/ln 2)k log2 k tests and is optimal among all nonadaptive designs in this regime.
Rates and algorithms: SSS is information-theoretically optimal under the i.i.d. prior because it is equivalent to maximum a posteriori estimation, but its smallest-satisfying-set computation is generally NP-hard.The set-cover formulation explains why SSS is useful as a benchmark despite high worst-case decoding complexity.
Rates and algorithms: COMP always returns a satisfying set with no false negatives, whereas DD has no false positives but may return an estimate that is not satisfying.In the illustrated DD failure, all items are marked possibly defective but no test contains a single item, yielding an empty estimate.
Rates and algorithms: COMP with optimized Bernoulli parameter p = 1/k achieves its stated rate using T ≥ (1 + η)ek ln n tests, while remaining robust to multiplicative misspecification of k.With an erroneous estimate k/c, COMP still achieves a nonzero rate, approaching the correctly specified rate as c approaches 1.

Algorithms for Noisy Group Testing

The noisy group-testing results combine information-theoretic capacity bounds with practical decoding algorithms, revealing model- and sparsity-dependent gaps between achievable rates and optimal limits. Comparisons show that noisy DD and separate decoding can outperform NCOMP in the displayed setting, while BP and LP perform best in a small simulation.

Information-theoretic limits: The noisy defective channel property yields capacity bounds for both adaptive and nonadaptive group testing, with C ≤ 1 − h(ρ) for the binary symmetric model.The property applies to several noise models but not the dilution or threshold models.
Information-theoretic limits: For the erasure model with k = o(n), adaptive group testing has capacity C = 1 − ξ.
Algorithmic rates: For k = Θ(n^α), DD and SSS provide explicit noisy-rate benchmarks, while COMP achieves rate 1 − φ under addition noise.The DD and SSS statements are presented as consequences of earlier noiseless results; the COMP extension uses definitive negative outcomes.
Algorithmic rates: Separate decoding is within an ln 2 factor of optimal when k = O(1), attaining ln 2 ≃ 0.693 bits/test in the noiseless setting.For noiseless and binary symmetric noise models, the stated factor compares separate decoding with the optimal joint decoder.
Algorithm comparisons: Noisy DD matches the Bernoulli-testing converse for addition noise across a wide α range, but wider gaps remain for the Z and symmetric noise models.In the low-noise limit, rates converge to the noiseless DD rate, although visible gaps can remain.

Information-Theoretic Limits

The monograph characterizes information-theoretic achievability and converse limits for noiseless group testing, including exact rates for Bernoulli and near-constant designs and polynomial-time attainment of the optimal rate. Nonadaptive testing reaches the counting-bound rate in limited sparsity regimes, while higher sparsity creates gaps for some designs.

Information-theoretic achievability and converse bounds characterize group-testing limits independently of computational complexity.
Bernoulli design: Bernoulli testing has an achievable rate matching or improving all algorithms considered in the monograph.
Bernoulli design: The exact maximum achievable rate for nonadaptive Bernoulli testing is established by a matching converse bound.
Near-constant column weight design: Near-constant column weight designs improve the noiseless achievable rate and attain their design-specific optimum.
Optimality and efficient decoding: The optimal rate RNCC is achievable with polynomial-time decoding using a modified spatially coupled test design.
Rate regimes: For α ≤1/3 with Bernoulli designs and α ≤0.409 with near-constant designs, nonadaptive testing achieves rate 1, matching the counting bound.

Discussion of achievability proof

The achievability analysis uses information-theoretic techniques, including concentration of information densities and mutual-information identities, to establish reliable recovery thresholds.

Achievability proofs analyze concentration of information densities around conditional mutual information.
For constant k, concentration bounds extend to general noise models and suffice for the relevant achievability argument.
The proof decomposes defective-item test columns and uses chain rules, independence, symmetry, and conditioning to relate mutual-information terms.

Discussion of converse proof

Converse proofs combine Fano-type bounds, genie arguments, and concentration or masking analyses to limit recovery rates, while noisy results refine the dominant error events and design thresholds.

General converse strategy: Fano’s inequality bounds the information needed to identify the defective set, with independent tests converting total information into T times per-test mutual information.
General converse strategy: The resulting bound matches the achievability expression when its maximum occurs at τ = k, but not necessarily otherwise.
General converse strategy: Genie arguments reveal part of the defective set, yielding stronger converses by bounding recovery of the unrevealed items and maximizing over their number.
Noisy converse and achievability: Under symmetric noise, exact thresholds were obtained for Bernoulli and near-constant column weight designs, with improvements over earlier achievable rates.
Noisy converse and achievability: Existing noisy DD approaches are strictly suboptimal under symmetric noise, whereas spatial coupling can attain matching thresholds with polynomial-time decoding.
Noisy converse and achievability: Noisy converse analysis replaces complete masking with events involving insufficient unique-defective tests and misleading nondefective items.

Overview of results

The surveyed results span efficient adaptive and nonadaptive algorithms, optimal-rate characterizations, noisy settings, and broader sparsity regimes. Together, they establish scaling guarantees and rate consequences while identifying computational and regime-dependent limitations.

Efficient algorithms: O(k log n) tests and O(k log n) decoding time are achieved by adaptive GROTESQUE and binary splitting, with vanishing error probability.Adaptive GROTESQUE uses O(log n) stages, while binary splitting provides the same asymptotic test and decoding-time scaling.
Efficient algorithms: Nonadaptive GROTESQUE uses O(k log n log k) tests and O(k(log n + log2 k)) decoding time, matching SAFFRON in test count up to constants but having zero rate.Its scaling is only a logarithmic factor from optimality, and its adaptive observation procedure can leave some tests unobserved.
Efficient algorithms: O(k(log n + log2 k)) tests and decoding time are achieved by two-stage GROTESQUE, yielding positive rate when log2 k = O(log n).This condition does not hold for k = Θ(nα), the regime emphasized in the monograph.
Nonadaptive testing: Exact recovery with O(k log n) tests and sublinear decoding is addressed by BMC, while concurrent strategies attain O(k log n) in both tests and decoding time.BMC has O(k2 log k log n) decoding time, whereas the order-optimal nonadaptive strategies achieve matching test and decoding-time scaling.
The linear regime: In the linear regime, nonadaptive individual testing is rate-optimal with capacity h(β), while T < (1 −η)n forces error probability toward one.The capacity satisfies h(β) ≤ C(β) ≤ 1, and refinement results extend the impossibility beyond the strictly linear regime.

Zero-error combinatorial setting

The surveyed results establish strong guarantees for zero-error and small-error group testing across sparsity regimes, priors, and testing constraints. Binary splitting can approach high rates in linear regimes, while adaptive, structured, and graph-constrained designs provide additional guarantees.

Linear-regime binary splitting: A rate of at least 0.9 is achieved for all β ≤ 1/2 by binary splitting under the combinatorial prior.The rate exhibits bumps because the optimal integer parameter s changes with β.
Comparison with individual testing: Individual testing is suboptimal when β < 1/3, while a converse establishes its optimality under the i.i.d. prior for β ≥ β∗ ≈ 0.382.For the combinatorial prior, individual testing is known to be optimal for β ≥ 1 − log_3 2 ≈ 0.369.
Linear-regime binary splitting: A rate of at least 0.95 is achieved for all β ≤ 1/2 under the i.i.d. prior.The number of tests concentrates around its average: for any ϵ > 0, it is at most (1 + ϵ)ET with probability approaching 1.
Non-uniform priors: In non-identical prior models, an entropy benchmark of H_n tests is necessary, and rate 1 is achievable under suitable conditions when k_n/H_n → 0.The corresponding algorithm is a non-identical analogue of generalized binary splitting.
Structured populations: Community-aware adaptive testing can match the lower bound asymptotically when k_f ≪ F, k_m = M/2, and M ≫ 1.In the extreme case k_m = M, the leading dependence can reduce from k = k_f k_m to k_f.
Path constraints: Graph-constrained designs use random walks to satisfy path constraints and require O(k^2τ(n)^2 log n) tests for zero-error recovery.For expander and certain Erdős–Rényi graphs, τ(n) = O(log n), so the constraints do not considerably increase the required tests.

Evidence from local search algorithms

The survey reports evidence of a computational-statistical gap in sparse group testing: information-theoretically optimal rates may be inaccessible to local-search and low-degree polynomial methods. It also contrasts these asymptotic barriers with favorable finite-size simulations and surveys non-binary extensions.

Local search: Follow-up analysis suggests local search algorithms cannot attain a rate exceeding ln 2, despite earlier evidence pointing toward optimal thresholds.The refined analysis attributes the earlier contrary evidence to averages dominated by rare events.
Finite-size behavior: The asymptotic local-search results may not predict small- or moderate-size behavior, where Glauber-dynamics local search matched SSS in simulations.These simulations also found local methods could outperform COMP, DD, and separate decoding in practice.
Low-degree polynomial methods: For constant-column-weight designs, degree-D polynomial algorithms fail weak separation below the threshold c < 1/ln 2, suggesting exp(n^Ω(1)) runtime.As α → 0, the corresponding rate threshold approaches ln 2 ≈ 0.693, matching COMP.
Computational-statistical gap: Overall evidence points to a computational-statistical gap for small α, although local and low-degree polynomial methods do not exhaust all possible algorithms.Thus, other computational approaches could still outperform these method classes.
Non-binary models: Quantitative testing can reduce the optimal test count because each outcome may reveal O(log k) bits rather than one bit, yielding O(k) tests in sparse regimes.This differs from standard binary group testing, whose sparse-regime scale is higher.
Tropical group testing: Tropical DD can require significantly fewer tests than tropical COMP and classical DD, and is asymptotically optimal in certain parameter regimes.Tropical COMP instead has the same asymptotic test count as the binary case under Bernoulli designs.