Adaptive group testing as channel coding with feedback

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

4 pages, 1 figure

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Adaptive group testing as channel coding with feedback does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Adaptive group testing as channel coding with feedback, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive group testing as channel coding with feedback will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-640537

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.