2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | C.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
