Quantitative Group Testing in the Sublinear Regime: Information-Theoretic and Algorithmic Bounds

The quantitative group testing (QGT) problem deals with efficiently identifying a small number of infected individuals among a large population. To this end, we can test groups of individuals where each test returns the total number of infected individuals in the tested group. For the regime where the number of infected individuals is sublinear in the population size we derive a sharp information-theoretic threshold for the minimum number of tests required to identify the infected individuals with high probability. Such a threshold was so far only known for the case where the infected individuals form a constant fraction of the population (Alaoui et al. 2014, Scarlett & Cevher 2017). Moreover, we propose and analyze a simple and efficient greedy reconstruction algorithm that matches the performance guarantees of much more involved constructions (Karimi et al. 2019).