Improved group testing rates with constant column weight designs

Matthew P Aldridge, Oliver T Johnson, Jonathan Scarlett

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

2 Citations (Scopus)
254 Downloads (Pure)

Abstract

We consider nonadaptive group testing where each item is placed in a constant number of tests. The tests are chosen uniformly at random with replacement, so the testing matrix has (almost) constant column weights. We show that performance is improved compared to Bernoulli designs, where each item is placed in each test independently with a fixed probability. In particular, we show that the rate of the practical COMP detection algorithm is increased by 31% in all sparsity regimes. In dense cases, this beats the best possible algorithm with Bernoulli tests, and in sparse cases is the best proven performance of any practical algorithm. We also give an algorithm-independent upper bound for the constant column weight case; for dense cases this is again a 31% increase over the analogous Bernoulli result.
Original languageEnglish
Title of host publication2016 IEEE International Symposium on Information Theory (ISIT 2016)
Subtitle of host publicationProceedings of a meeting held 10-15 July 2016 at Barcelona, Spain
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1381-1386
Number of pages5
ISBN (Electronic)9781509018062
ISBN (Print)9781509018079
DOIs
Publication statusPublished - 20 Aug 2016
Event2016 IEEE International Symposium on Information Theory (ISIT) - Barcelona, Spain
Duration: 10 Jul 201615 Jul 2016

Publication series

NameProceedings of the IEEE International Symposium on Information Theory (ISIT)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
ISSN (Print)2157-8117

Conference

Conference2016 IEEE International Symposium on Information Theory (ISIT)
CountrySpain
CityBarcelona
Period10/07/1615/07/16

Fingerprint Dive into the research topics of 'Improved group testing rates with constant column weight designs'. Together they form a unique fingerprint.

Cite this