On the optimality of some group testing algorithms

Matthew Aldridge

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)
37 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of 2017 IEEE International Symposium on Information Theory (ISIT)
PublisherIEEE
Pages3085-3089
ISBN (Electronic)2157-8117
DOIs
Publication statusPublished - Jun 2017
Event2017 IEEE International Symposium on Information Theory (ISIT) - Aachen, Germany
Duration: 25 Jun 201730 Jun 2017

Conference

Conference2017 IEEE International Symposium on Information Theory (ISIT)
Period25/06/1730/06/17

Fingerprint Dive into the research topics of 'On the optimality of some group testing algorithms'. Together they form a unique fingerprint.

Cite this