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 \({\it \Omega}(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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Du, D.Z., Hwang, F.: Combinatorial Group Testing and its Applications, 2nd edn. World Scientific, Singapore (2000)
Du, D.-Z., Hwang, F.K.: Pooling Designs and Nonadaptive Group Testing. World Scientific, Singapore (2006)
Knill, E.: Lower bounds for identifying subset members with subset queries. In: Proceedings of SODA, pp. 369–377 (1995)
Dyachkov, A., Rykov, V.: A survey of superimposed code theory. Problems of Control and Information Theory 12(4), 229–242 (1983)
Knill, E., Bruno, W.J., Torney, D.C.: Non-adaptive group testing in the presence of errors. Discrete Appl. Math. 88(1–3), 261–290 (1998)
D’yachkov, A.G., Rykov, V.: Bounds of the length of disjunct codes. Problems of Control and Information Theory 11, 7–13 (1982)
Ruszinkó: On the upper bound of the size of the r-cover-free families. J. Comb. Theory., Series A 66, 302–310 (1994)
Füredi, Z.: On r-cover-free families. J. Comb. Theory, Series A 73, 172–173 (1996)
Kautz, W., Singleton, R.: Nonrandom binary superimposed codes. IEEE Transactions on Information Theory 10, 363–377 (1964)
Macula, A.: Probabilistic nonadaptive and two-stage group testing with relatively small pools and DNA library screening. J. Comb. Optim. 2, 385–397 (1999)
Berger, T., Mandell, J., Subrahmanya, P.: Maximally efficient two-stage group testing. Biometrics 56, 833–840 (2000)
De Bonis, A., Gasieniec, L., Vaccaro, U.: Optimal two-stage algorithms for group testing problems. SIAM Journal on Computing 34(5), 1253–1270 (2005)
Eppstein, D., Goodrich, M., Hirschberg, D.: Improved combinatorial group testing algorithms for real-world problem sizes. SIAM J. Comp. 36(5), 1360–1375 (2007)
Cheng, Y., Du, D.Z.: New constructions of one- and two-stage pooling designs. Journal of Computational Biology 15(2), 195–205 (2008)
Indyk, P.: Explicit constructions of selectors with applications. In: Proceedings of SODA (2002)
Chlebus, B., Kowalski, D.: Almost optimal explicit selectors. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 270–280. Springer, Heidelberg (2005)
Ta-Shma, A., Zuckerman, D.: Extractor codes. IEEE Transactions on Information Theory 50(12), 3015–3025 (2004)
Guruswami, V., Umans, C., Vadhan, S.: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. In: Proc. of the 22nd IEEE CCC (2007)
Radhakrishan, J., Ta-Shma, A.: Tight bounds for depth-two superconcentrators. In: Proceedings of the 38th FOCS, pp. 585–594 (1997)
Capalbo, M., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant-degree expansion beyond the degree/2 barrier. In: Proceedings of the 34th STOC, pp. 659–668 (2002)
Trevisan, L.: Extractors and pseudorandom generators. Journal of the ACM 48(4), 860–879 (2001)
Raz, R., Reingold, O., Vadhan, S.: Extracting all the randomness and reducing the error in Trevisan’s extractor. JCSS 65(1), 97–128 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cheraghchi, M. (2009). Noise-Resilient Group Testing: Limitations and Constructions. In: Kutyłowski, M., Charatonik, W., Gębala, M. (eds) Fundamentals of Computation Theory. FCT 2009. Lecture Notes in Computer Science, vol 5699. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03409-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-03409-1_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03408-4
Online ISBN: 978-3-642-03409-1
eBook Packages: Computer ScienceComputer Science (R0)