Imperial College London

Dr Mahdi Cheraghchi

Faculty of EngineeringDepartment of Computing

Honorary Senior Lecturer



m.cheraghchi Website CV




353ACE ExtensionSouth Kensington Campus






BibTex format

author = {Bui, TV and Kuribayashil, M and Cheraghchi, M and Echizen, I},
doi = {10.1109/ISIT.2018.8437847},
pages = {2584--2588},
publisher = {IEEE},
title = {Efficiently decodable non-adaptive threshold group testing},
url = {},
year = {2018}

RIS format (EndNote, RefMan)

AB - 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.
AU - Bui,TV
AU - Kuribayashil,M
AU - Cheraghchi,M
AU - Echizen,I
DO - 10.1109/ISIT.2018.8437847
EP - 2588
PY - 2018///
SN - 2157-8095
SP - 2584
TI - Efficiently decodable non-adaptive threshold group testing
UR -
UR -
ER -