Repository logo
  • Log In
    Log in via Symplectic to deposit your publication(s).
Repository logo
  • About
  • Communities & Collections
  • Advanced Search
  • Statistics
  • Log In
    Log in via Symplectic to deposit your publication(s).
  1. Home
  2. Faculty of Engineering
  3. Faculty of Engineering
  4. Noise-resilient group testing: limitations and constructions
 
  • Details
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
URI
http://hdl.handle.net/10044/1/63204
DOI
https://www.dx.doi.org/10.1007/978-3-642-03409-1_7
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
About
Spiral Depositing with Spiral Publishing with Spiral Symplectic
Contact us
Open access team Report an issue
Other Services
Scholarly Communications Library Services
logo

Imperial College London

South Kensington Campus

London SW7 2AZ, UK

tel: +44 (0)20 7589 5111

Accessibility Modern slavery statement Cookie Policy

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback