Type of Talk: ACT Seminar

Speaker/Affiliation: Mahdi Chera

ghchi/UT Austin

Date/Time: Tuesday, November 9, 2010 4:00 p.m.

Location: ACES 3.408

Host: David Zuckerman

Talk Title: Noise-resi

lient Group Testing

Talk Abstract:
We study combinatorial group test

ing schemes for learning d-sparse Boolean vectors using highly unreliable d

isjunctive measurements. We consider an adversarial noise model that only l

imits the number of false observations, and show that any noise-resilient

scheme in this model can only approximately reconstruct the sparse vector.

We study a general framework for construction of highly noise-resilien

t group testing schemes using randomness condensers. Simple randomized inst

antiations of this construction give non-adaptive measurement schemes, wit

h m=O(d*log(n)) measurements, that allow efficient reconstruction of d-spa

rse vectors up to O(d) false positives even in the presence of c*m false po

sitives and Omega(m/d) false negatives within the measurement outcomes, fo

r any constant c<1. None of these parameters can be substantially improve

d without dramatically affecting the others. Furthermore, we obtain severa

l explicit (and incomparable) constructions, in particular one matching th

e randomized trade-off but using m=O(d^(1+o(1))*log(n)) measurements. We a

lso obtain explicit constructions that allow fast reconstruction in time po

lynomial in m, which would be sublinear in n for sufficiently sparse vecto

rs.