Optimal group testing
Amin Coja‐Oghlan, Oliver Gebhard, Max Hahn‐Klimroth, Philipp Loick
Abstract
Abstract In the group testing problem the aim is to identify a small set of k ⁓ n θ infected individuals out of a population size n , 0 < θ < 1. We avail ourselves of a test procedure capable of testing groups of individuals, with the test returning a positive result if and only if at least one individual in the group is infected. The aim is to devise a test design with as few tests as possible so that the set of infected individuals can be identified correctly with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition m inf for non-adaptive group testing, where all tests are conducted in parallel. Thus with more than m inf tests the infected individuals can be identified in polynomial time with high probability, while learning the set of infected individuals is information-theoretically impossible with fewer tests. In addition, we develop an optimal adaptive scheme where the tests are conducted in two stages.