Group Testing

In the group testing problem we aim to identify a small number of infected individuals within a large population. At our disposal we have a test procedure that returns the infection status of not just one individual, but of an entire group. Specifically, the test result is positive if any one individual in the group is infected, and negative otherwise. All tests are conducted in parallel. The task is to find a test design, i.e., an allocation of individuals to tests, such that the infection status of each individual can be inferred from the test results. Each individual can be assigned to several tests, and randomisation is allowed. Within this framework, what is the smallest number of tests required to infer the infection status of all individuals with high probability, either algorithmically or information-theoretically?

The talk is based on recent joint work with Oliver Gebhard, Max Hahn-Klimroth and Philipp Loick.