Improved Constructions for Non-adaptive Threshold Group Testing

Improved Constructions for Non-adaptive Threshold Group Testing. Cheraghchi, M. Algorithmica, 67:384–417, 2013. Preliminary version in Proceedings of ICALP 2010.

Link

Slides

Paper doi abstract bibtex

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 reaches a fixed threshold $u > 0$, negative if this number is no more than a fixed lower threshold $\ell < 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} (łog d) łog(n/d))$ measurements (where $g := u-\ell-1$ and $u$ is any fixed constant) 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} łog(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} (łog d) łog n)$. Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with $O(d^{g+3} (łog d) \mathrm{quasipoly}(łog n))$ and $O(d^{g+3+β}\mathrm{poly}(łog n))$ measurements, for arbitrary constant $β > 0$.

@ARTICLE{ref:Che13,
  author =	 {Cheraghchi, Mahdi},
  title =	 {Improved Constructions for Non-adaptive Threshold
                  Group Testing},
  year =	 2013,
  volume =	 67,
  url_Link =
                  {https://link.springer.com/article/10.1007/s00453-013-9754-7},
  url_Slides =	 {http://www.ima.umn.edu/videos/?id=1803},
  doi =		 {10.1007/s00453-013-9754-7},
  journal =	 {Algorithmica},
  pages =	 {384--417},
  keywords =	 {Threshold group testing, Lossless expanders,
                  Combinatorial designs, Explicit constructions},
  note =	 {Preliminary version in {Proceedings of ICALP 2010.}},
  url_Paper =	 {https://arxiv.org/abs/1002.2244},
  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 \gg 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 reaches a fixed
                  threshold $u > 0$, negative if this number is no
                  more than a fixed lower threshold $\ell < 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-1$ and $u$ is any fixed constant)
                  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 obtain explicit testing
                  schemes with $O(d^{g+3} (\log d)
                  \mathrm{quasipoly}(\log n))$ and
                  $O(d^{g+3+\beta}\mathrm{poly}(\log n))$
                  measurements, for arbitrary constant $\beta > 0$.}
}

Downloads: 0