2020/06/02 by Bay, Wei Heng, Price, Eric, Scarlett, Jonathan
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)
paper · doi:10.48550/arxiv.2006.01325
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 in the case of n items among which k are defective, the smallest possible number of tests equals min\ Ck,n k log n, n\ up to lower-order asymptotic terms, where Ck,n is a uniformly bounded constant (varying depending on the scaling of k with respect to n) with a simple explicit expression. 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 ≤ n1-Ω(1) and k = Θ(n). In sufficiently sparse regimes (including k = o( (n)/(log n) )), our main result generalizes that of Coja-Oghlan \em et al. (2020) by avoiding the assumption k ≤ n1-Ω(1), whereas in sufficiently dense regimes (including k = ω( (n)/(log n) )), 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.