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 $\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.

Publié dans:
Proceedings of the 17th International Symposium on Fundamentals of Computation Theory (FCT), 62--73
Présenté à:
17th International Symposium on Fundamentals of Computation Theory (FCT), Wroclaw, Poland, 2009

Note: Le statut de ce fichier est: Seulement EPFL

 Notice créée le 2009-09-30, modifiée le 2019-08-12

Télécharger le documentPDF
Lien externe:
Télécharger le documentURL
Évaluer ce document:

Rate this document:
(Pas encore évalué)