Improved Constructions for Non-adaptive Threshold Group Testing

Details Improved Constructions for Non-adaptive Threshold Group Testing Improved Constructions for Non-adaptive Threshold Group Testing

2010-02-10

arxiv.org/abs/1002.2244v2

Computer Science

Discrete Mathematics

Draft of the full version. Preliminary version appeared in Proceedings of the 37th International Colloquium on Automata, Langu

Scientific paper

The 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 $\ell \leq 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-\ell$) 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$.

Affiliated with

Also associated with

No associations

Rating

Improved Constructions for Non-adaptive Threshold Group Testing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Constructions for Non-adaptive Threshold Group Testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Constructions for Non-adaptive Threshold Group Testing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67808