Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes

In this paper, we consider the problem of noiseless non-adaptive probabilistic group testing, in which the goal is high-probability recovery of the defective set. We show that the smallest possible number of tests behaves as $\Theta( \min\{k \log n, n\} )$ in the case of $n$ items among which $k$ are defective, as well as providing the precise underlying constant factors. The algorithmic upper bound follows from a minor adaptation of an existing analysis of the Definite Defectives (DD) algorithm, and the algorithm-independent lower bound builds on existing works for the regimes $k \le n^{1-\Omega(1)}$ and $k = \Theta(n)$. In sufficiently sparse regimes (including $k = o\big( \frac{n}{\log n} \big)$), our main result generalizes that of Coja-Oghlan {\em et al.} (2020) by avoiding the assumption $k \le n^{1-\Omega(1)}$, whereas in sufficiently dense regimes (including $k = \omega\big( \frac{n}{\log n} \big)$), our main result shows that individual testing is asymptotically optimal for any non-zero target success probability, thus strengthening an existing result of Aldridge (2019) in terms of both the error probability and the assumed scaling of $k$.