Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes

DOI10.1093/IMAIAI/IAAB020zbMATH Open1528.62012arXiv2006.01325MaRDI QIDQ6341875FDOQ6341875

Authors: Wei Heng Bay, Jonathan Scarlett, Eric Price 

Publication date: 1 June 2020

Abstract: 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{C}_{k,n}klogn,n$ up to lower-order asymptotic terms, where $C_{k,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 $kle{n}^{1-Omega(1)}$ and $k=Theta(n)$. In sufficiently sparse regimes (including $$), our main result generalizes that of Coja-Oghlan {em et al.} (2020) by avoiding the assumption $kle{n}^{1-Omega(1)}$, whereas in sufficiently dense regimes (including $$), 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$.

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Randomized algorithms (68W20)

This page was built for publication: Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341875)