This shows you the differences between two versions of the page.

Link to this comparison view

en:group:seminars:tmp:20090114 [2016/06/23 11:26] (current)
Line 1: Line 1:
 +---- dataentry seminar ----
 +date_dt : 2009.01.14
 +title : Noise-Resilient Group Testing: Limitations and Constructions
 +speaker : Mahdi Cheraghchi
 +affiliation :  ALGO
 +time : 16h15-17h15
 +room : BC129
 +table : seminars
 +==== 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 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 $\Omega(d^{2} \log(n)/​\log(d))$ that is known for exact reconstruction of $d$-sparse vectors of length $n$ via non-adaptive measurements,​ by a multiplicative factor of almost linear in $d$.  \\ Specifically,​ we give simple randomized constructions of 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 $\deltam$ false positives and $O(m/d)$ false negatives within the measurement outcomes, for any constant $\delta < 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(d^{1+o(1)}\log(n))$ measurements. ​  We also obtain explicit constructions that allow fast reconstruction in time polynomial in $m$, which would be sublinear in $n$ for sufficiently sparse vectors. ​ \\ An immediate consequence of our result is an adaptive scheme that runs in only two non-adaptive "​rounds"​ and exactly reconstructs any $d$-sparse vector using a total $O(d \log(n))$ measurements,​ a task that would be impossible in one round and fairly easy in $O(\log(n/​d))$ rounds.