Noise-resilient group testing: limitations and constructions
File(s)0811.2609v3.pdf (570.84 KB)
Accepted version
Author(s)
Cheraghchi, Mahdi
Type
Conference Paper
Abstract
We study combinatorial group testing schemes for learning d-sparse boolean vectors using highly unreliable disjunctive measurements. We consider an adversarial noise model that only limits the number of false observations, and show that any noise-resilient scheme in this model can only approximately reconstruct the sparse vector. On the positive side, we give a general framework for construction of highly noise-resilient group testing schemes using randomness condensers. Simple randomized instantiations of this construction give non-adaptive measurement schemes, with m = O(d logn) measurements, that allow efficient reconstruction of d-sparse vectors up to O(d) false positives even in the presence of δm false positives and Ω(m/d) false negatives within the measurement outcomes, for any constant δ< 1. None of these parameters can be substantially improved without dramatically affecting the others. Furthermore, we obtain several explicit (and incomparable) constructions, in particular one matching the randomized trade-off but using m = O(d 1 + o(1) logn) measurements. We also obtain explicit constructions that allow fast reconstruction in time poly(m), which would be sublinear in n for sufficiently sparse vectors.
Editor(s)
Kutylowski, M
Charatonik, W
Gebala, M
Date Issued
2009-09-04
Date Acceptance
2009-09-02
Citation
Fundamentals of Computation Theory, 2009, 5699, pp.62-73
ISBN
978-3-642-03408-4
ISSN
0302-9743
Publisher
Springer VERLAG
Start Page
62
End Page
73
Journal / Book Title
Fundamentals of Computation Theory
Volume
5699
Copyright Statement
© 2009 Springer-Verlag. The final publication is available at Springer via https://dx.doi.org/10.1007/978-3-642-03409-1_7
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000270320900006&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Source
17th International Symposium on Fundamentals of Computation Theory
Subjects
Science & Technology
Technology
Computer Science, Theory & Methods
Computer Science
COVER-FREE FAMILIES
ALGORITHMS
EXTRACTORS
CODES
Publication Status
Published
Start Date
2009-09-02
Finish Date
2009-09-04
Coverage Spatial
Wroclaw Univ Technol, Wroclaw, Poland
Date Publish Online
2009-09-02