Matthew Aldridge

Group testing in the linear regime

Suppose you wish to use a blood test to screen a group of people for a rare disease. You could take a blood sample from each person and test the samples individually. However, it can be more efficient to mix a number of samples together and test that mixture: if the test comes back negative then none of those people have the disease, while if the test is positive then at least one of them has the disease and further investigation is needed. This problem is called group testing: given n people of whom k have the disease, how many tests do we need to find out which people are infected?

In this talk, we discuss the case where n tends to infinity and k grows linearly with n. We are interested in the question of when individual testing is optimal. The answer will depend on whether we design all tests at the start or can choose tests as we go, and whether we want to be certain to have accurate detection or are happy with error probability tending to 0.