On the optimality of some group testing algorithms

Abstract

We consider Bernoulli nonadaptive group testing with $k=\Theta (n^{\theta })$ defectives, for $\theta \in (0,1)$. The practical definite defectives (DD) detection algorithm is known to be optimal for $\theta \ge 1/2$. We give a new upper bound on the rate of DD, showing that DD is strictly suboptimal for $\theta <0.41$. We also show that the SCOMP algorithm and algorithms based on linear programming achieve a rate at least as high as DD, so in particular are also optimal for $\theta \ge 1/2$.

To be presented at ISIT 2017. 5 pages, 2 figures