Efficiently Decodable Non-Adaptive Threshold Group Testing

Abstract

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\le u\le 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(n\log n+n\log \frac{1}{\epsilon })$ for probabilistic decoding, where $\epsilon >0$, and $O(n^u\log n)$ for deterministic decoding.