000151699 001__ 151699
000151699 005__ 20190117210902.0
000151699 02470 $$2ISI$$a000286345400047
000151699 037__ $$aCONF
000151699 245__ $$aImproved Constructions for Non-adaptive Threshold Group Testing
000151699 269__ $$a2010
000151699 260__ $$bSpringer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa$$c2010
000151699 336__ $$aConference Papers
000151699 490__ $$aLecture Notes in Computer Science
000151699 520__ $$aThe basic goal in combinatorial group testing is to identify a set of up to d defective items within a large population of size n >> d using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool passes a fixed threshold u, negative if this number is below a fixed lower threshold L <= u, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, O(d^{g+2} (\log d) log(n/d)) measurements (where g := u-L) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known non-constructive) upper bound O(d^{u+1} log(n/d)). Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by O(d^{g+3} (\log d) \log n). Using state-of-the-art constructions of lossless condensers, however, we come up with explicit testing schemes with O(d^{g+3} (\log d) quasipoly(log n)) and O(d^{g+3+beta} poly(log n)) measurements, for arbitrary constant beta > 0.
000151699 6531_ $$aalgo_misc
000151699 700__ $$aCheraghchi, Mahdi
000151699 7112_ $$a37th International Colloquium on Automata, Languages and Programming (ICALP)$$cBordeaux, France$$dJuly 5-10, 2010
000151699 773__ $$tProceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)
000151699 909C0 $$0252198$$pALGO$$xU10735
000151699 909CO $$ooai:infoscience.tind.io:151699$$pconf$$pIC
000151699 917Z8 $$x166246
000151699 917Z8 $$x166246
000151699 937__ $$aEPFL-CONF-151699
000151699 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000151699 980__ $$aCONF