Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars

Abstract

We modify Cheraghchi-Nakos [CN20] and Price-Scarlett's [PS20] fast binary splitting approach to nonadaptive group testing. We show that, to identify a uniformly random subset of $k$ infected persons among a population of $n$, it takes only $\ln (2-4\epsilon {)}^{-2}k\ln n$ tests and decoding complexity $O({\epsilon }^{-2}k\ln n)$, for any small $\epsilon >0$, with vanishing error probability. In works prior to ours, only two types of group testing schemes exist. Those that use $\ln (2{)}^{-2}k\ln n$ or fewer tests require linear-in-$n$ complexity, sometimes even polynomial in $n$; those that enjoy sub-$n$ complexity employ $O(k\ln n)$ tests, where the big-$O$ scalar is implicit, presumably greater than $\ln (2{)}^{-2}$. We almost achieve the best of both worlds, namely, the almost-$\ln (2{)}^{-2}$ scalar and the sub-$n$ decoding complexity. How much further one can reduce the scalar $\ln (2{)}^{-2}$ remains an open problem.

arXiv comment6 pages, 3 figures, ISIT 2023