Noise-resilient group testing: Limitations and constructions
We study combinatorial group testing schemes for learning d 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 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 ? ? ( d 2 log n ) that is known for exact reconstruction of d d -sparse vectors of length n n 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 ( d log n ) measurements, that allow efficient reconstruction ofd d -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 ( 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 n 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 d d -sparse vector using a total O(dlogn) O ( d log n ) measurements, a task that would be impossible in one round and fairly easy in O(log(n/d)) O ( log ( n / d ) ) or d d rounds.
group testing randomness condensers extractors list decoding