Imperial College London
Portrait Picture

Dr Mahdi Cheraghchi

Faculty of Engineering, Department of Computing

Honorary Senior Lecturer
 
 
 
//

Contact

 

m.cheraghchi Website CV

 
 
//

Location

 

353ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inproceedings{Cheraghchi:2009:10.1007/978-3-642-03409-1_7,
author = {Cheraghchi, M},
doi = {10.1007/978-3-642-03409-1_7},
pages = {62--73},
publisher = {Springer VERLAG},
title = {Noise-resilient group testing: limitations and constructions},
url = {http://dx.doi.org/10.1007/978-3-642-03409-1_7},
year = {2009}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - 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.
AU  - Cheraghchi,M
DO  - 10.1007/978-3-642-03409-1_7
EP  - 73
PB  - Springer VERLAG
PY  - 2009///
SN  - 0302-9743
SP  - 62
TI  - Noise-resilient group testing: limitations and constructions
UR  - http://dx.doi.org/10.1007/978-3-642-03409-1_7
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000270320900006&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - http://hdl.handle.net/10044/1/63204
ER  -
Download