Improved bounds for noisy group testing with constant tests per item

Gebhard, Oliver; Johnson, Oliver; Loick, Philipp; Rolvien, Maurice

The group testing problem is concerned with identifying a small set of infected individuals in a large population. At our disposal is a testing procedure that allows us to test several individuals together. In an idealized setting, a test is positive if and only if at least one infected individual is included and negative otherwise. Significant progress was made in recent years towards understanding the information-theoretic and algorithmic properties in this noiseless setting. In this paper, we consider a noisy variant of group testing where test results are flipped with certain probability, including the realistic scenario where sensitivity and specificity can take arbitrary values. Using a test design where each individual is assigned to a fixed number of tests, we derive explicit algorithmic bounds for two commonly considered inference algorithms and thereby improve on results by Scarlett \&Cevher (SODA 2016) and Scarlett \&Johnson (2020) and providing the strongest performance guarantees currently proved for efficient algorithms in these noisy group testing models.