Adaptive group testing as channel coding with feedback

Matthew P Aldridge

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

10 Citations (Scopus)

Abstract

Group testing is the combinatorial problem of identifying the defective items in a population by grouping items into test pools. Recently, nonadaptive group testing - where all the test pools must be decided on at the start - has been studied from an information theory point of view. Using techniques from channel coding, upper and lower bounds have been given on the number of tests required to accurately recover the defective set, even when the test outcomes can be noisy. In this paper, we give the first information-theoretic result on adaptive group testing - where the outcome of previous tests can influence the makeup of future tests. We show that adaptive testing does not help much, as the number of tests required obeys the same lower bound as nonadaptive testing. Our proof uses similar techniques to the proof that feedback does not improve channel capacity.
Original languageEnglish
Title of host publicationIEEE International Symposium on Information Theory 2012 (ISIT), Cambridge MA, USA
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1832-1836
Number of pages5
ISBN (Print)978-1-4673-2579-0
DOIs
Publication statusPublished - 2012

Keywords

  • Adaptation models , Channel coding , Error probability , Mutual information , Noise measurement , Testing , Yttrium

Fingerprint Dive into the research topics of 'Adaptive group testing as channel coding with feedback'. Together they form a unique fingerprint.

Cite this