Noise-resilient group testing: Limitations and constructions

We study combinatorial group testing schemes for learning dd-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 take this barrier to our advantage and show that approximate reconstruction (within a satisfactory degree of approximation) allows us to break the information theoretic lower bound of Ω̃(d2logn) that is known for exact reconstruction of dd-sparse vectors of length nn via non-adaptive measurements, by a multiplicative factor Ω̃(d).Specifically, we give simple randomized constructions of non-adaptive measurement schemes, with m=O(dlogn)m=O(dlogn) measurements, that allow efficient reconstruction ofdd-sparse vectors up to O(d)O(d) false positives even in the presence of δmδm false positives and O(m/d)O(m/d) false negatives within the measurement outcomes, for any   constant δ<1δ<1. We show that, information theoretically, none of these parameters can be substantially improved without dramatically affecting the others. Furthermore, we obtain several explicit constructions, in particular one matching the randomized trade-off but using m=O(d1+o(1)logn)m=O(d1+o(1)logn) measurements. We also obtain explicit constructions that allow fast reconstruction in time poly(m), which would be sublinear in nn for sufficiently sparse vectors. The main tool used in our construction is the list-decoding view of randomness condensers and extractors.An immediate consequence of our result is an adaptive scheme that runs in only two non-adaptive rounds   and exactly reconstructs any dd-sparse vector using a total O(dlogn)O(dlogn) measurements, a task that would be impossible in one round and fairly easy in O(log(n/d))O(log(n/d)) or dd rounds.