Density-Dependent Group Testing

Group testing is the problem of identifying a small subset of defectives from a large set using as few binary tests as possible. In most current literature on group testing the binary test outcome is $1$ if the pool contains at least one defective, and $0$ otherwise. In this work we initiate the study of a generalized model of group testing that accommodates the physical effects of dilution of infected samples in large pools. In this model the binary test outcome is $1$ with probability $f(\rho)$, where $\rho$ is the density of the defectives in the test, and $f:[0,1]\rightarrow [0,1]$ is a given "test function" that models this dilution process. For a large class of test functions our results establish near-optimal sample complexity bounds, by providing information-theoretic lower bounds on the number of tests necessary to recover the set of defective items, and providing computationally efficient algorithms with sample complexities that match these lower bounds up to constant or logarithmic factors. Furthermore, using tools from real analysis, we extend our results to any "sufficiently well-behaved function" $f:[0,1]\rightarrow [0,1]$.