Noise-Resilient Group Testing: Limitations and Constructions
Mahdi Cheraghchi
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 log n) measurements, that allow efficient
reconstruction of d-sparse vectors up to O(d) false positives even in
the presence of (delta m) false positives and Omega(m/d) false negatives
within the measurement outcomes, for any constant delta < 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.