Efficient designs for threshold group testing without gap

Given d defective items in a population of n items with d 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 ≤ u ≤ 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)ᵘ (d/(d-u))d - u, d, and logn. In this work, we present a novel design that significantly reduces the number of tests and the decoding time to polynomials of minᵘ, (d - u)d - u\, d, and logn. In particular, when u is a constant, the number of tests and the decoding time are O(d³ (log²n) log(n/d) ) and O(d³ (log²n) log(n/d) + d² (logn) log³(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³ (logn) log(n/d) ) and O(d² (logn + log²(n/d)) ), respectively. Moreover, with 2-stage design, the number of tests and the decoding time are O(d² log²(n/d) ).