We consider Bernoulli nonadaptive group testing with k=Θ(n^θ) defectives, for θ∈(0,1). The practical definite defectives (DD) detection algorithm is known to be optimal for θ≥1/2. We give a new upper bound on the rate of DD, showing that DD is strictly suboptimal for θ<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 θ≥1/2.
|Title of host publication||Proceedings of 2017 IEEE International Symposium on Information Theory (ISIT)|
|Publication status||Published - Jun 2017|
|Event||2017 IEEE International Symposium on Information Theory (ISIT) - Aachen, Germany|
Duration: 25 Jun 2017 → 30 Jun 2017
|Conference||2017 IEEE International Symposium on Information Theory (ISIT)|
|Period||25/06/17 → 30/06/17|