Efficient designs for threshold group testing without gap

Abstract

Given $d$ defective items in a population of $n$ items with $d\ll n$, in threshold group testing without gap, the outcome of a test on a subset of items is positive if the subset has at least $u$ defective items and negative otherwise, where $1\le u\le d$. The basic goal of threshold group testing is to quickly identify the defective items via a small number of tests. In non-adaptive design, all tests are designed independently and can be performed in parallel. The decoding time in the non-adaptive state-of-the-art work is a polynomial of $(d/u{)}^u(d/(d-u){)}^{d-u},d$, and $\log n$. In this work, we present a novel design that significantly reduces the number of tests and the decoding time to polynomials of $\min \{u^u,(d-u{)}^{d-u}\},d$, and $\log n$. In particular, when $u$ is a constant, the number of tests and the decoding time are $O(d^3({\log }^{2}n)\log (n/d))$ and $O(d^3({\log }^{2}n)\log (n/d)+d^2(\log n){\log }^3(n/d))$, respectively. For a special case when $u=2$, with non-adaptive design, the number of tests and the decoding time are $O(d^3(\log n)\log (n/d))$ and $O(d^2(\log n+{\log }^2(n/d)))$, respectively. Moreover, with 2-stage design, the number of tests and the decoding time are $O(d^2{\log }^2(n/d))$.

11 pages, 2 figures