Efficiently Decodable Non-Adaptive Threshold Group Testing

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-ϵ$ for any $ϵ>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)$testswithprobability1.Thedecodingtimeis$t \times $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}$(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}{ϵ})$ for probabilistic decoding, where $ϵ>0$, and $O(n^u\log n)$ for deterministic decoding.