Improved Constructions for Non-adaptive Threshold Group Testing

Mahdi Cheraghchi Bashi Astaneh
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa, 2010
Conference paper

Abstract

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 L 0.

Official source

https://infoscience.epfl.ch/record/151699?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Noise-Resilient Group Testing: Limitations and Constructions

Mahdi Cheraghchi Bashi Astaneh

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.

Springer2009