Efficiently decodable non-adaptive threshold group testing - Bui,TV; Kuribayashil,M; Cheraghchi,M; Echizen,I (IEEE, 2018)
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 2leq uleq d defective items, and negative otherwise. The defective items can be identified using t=O(( frac d u) u(frac d d-u) d-u(ulogfrac d u+logfrac 1 )d 2log n) tests with probability at least 1- for any > 0 or t= Oleft(left(frac b uright) uleft(frac d d-uright) d-ucdot d 3log n cdot log frac n dright) tests with probability 1. The decoding time is ttimes poly (d 2log n). This result significantly improves the best known results for decoding non-adaptive threshold group testing: O(n log n+nlogfrac 1 ) for probabilistic decoding, where > 0, and O(n ulog n) for deterministic decoding.