Group Testing

Corresponds to Lecture topic 11. If only a small, unknown subset of $k$ items out of $n$ are “defective” (e.g. infected samples in a pandemic testing scenario, or faulty chips on a production line), testing pools of items at once — a positive result flags the pool as containing at least one defective — can identify all defectives using far fewer than $n$ tests. Covers the combinatorial design of non-adaptive test pools (a fixed testing matrix, decoded all at once from the results) versus adaptive strategies (where later tests can depend on earlier results), and the information-theoretic lower bound on the number of tests any strategy needs (each test yields at most one bit, so recovering which $k$ of $n$ items are defective needs at least $\log_2\binom nk$ bits’ worth of tests) — see information-theory-statistics for the general hypothesis-testing/estimation framework this lower bound instantiates.

Outline (TODO — flesh out each)

• The group testing problem
• Non-adaptive group testing — combinatorial designs
• Adaptive group testing
• Information-theoretic lower bounds on the number of tests