Noise-Resilient Group Testing: Limitations and Constructions

摘要

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 log n) measurements, that allow efficient reconstruction of d-sparse vectors up to O(d) false positives even in the presence of 8m 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)) log n) measurements. We also obtain explicit constructions that allow fast reconstruction in time poly(m), which would be sublinear in n for sufficiently sparse vectors.