Technical Program

Paper Detail

Paper IDC.10.3
Paper Title Strongly Explicit and Efficiently Decodable Probabilistic Group Testing
Authors Huseyin Atahan Inan, Ayfer Ozgur, Stanford University, United States
Session C.10: Topics in Coding Theory
Presentation Lecture
Track Coding for Communications
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract We consider the non-adaptive probabilistic group testing problem where $d$ random defective items are identified with high probability from a population of $N$ items by applying $t$ binary group tests. There has been recent progress towards developing explicit and efficiently decodable group testing schemes with $t = \Theta(d \log N)$ tests, which is known to be order-optimal for this setting when $d = O(N^{1 - \alpha})$ for some constant $\alpha > 0$. In particular, a recent work develops an explicit scheme while another one develops an efficiently decodable scheme for this setting, both with the order-optimal $t = \Theta(d \log N)$ tests. However, to the best of our knowledge, there is no order-optimal scheme that is both explicit and efficiently decodable. In this paper, we close this gap by introducing the first (strongly) explicit and efficiently decodable construction that is order-optimal for the non-adaptive probabilistic group testing problem.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!