We consider non-adaptive threshold group testing for identification of up to $d$ defective items in a set of $n$ items, where a test is positive if it contains at least $2 leq u leq d$ defective items, and negative otherwise. The defective items can be identified using $t = O left( left( frac{d}{u} right)^u left( frac{d}{d - u} right)^{d-u} left(u log{frac{d}{u}} + log{frac{1}{epsilon}} right) cdot d^2 log{n} right)$ tests with probability at least $1 - epsilon$ for any $epsilon > 0$ or $t = O left( left( frac{d}{u} right)^u left( frac{d}{d -u} right)^{d - u} d^3 log{n} cdot log{frac{n}{d}} right)$ tests with probability 1. The decoding time is $t times mathrm{poly}(d^2 log{n})$. This result significantly improves the best known results for decoding non-adaptive threshold group testing: $O(nlog{n} + n log{frac{1}{epsilon}})$ for probabilistic decoding, where $epsilon > 0$, and $O(n^u log{n})$ for deterministic decoding.
Download