2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | G.4.2 | ||
| Paper Title | Near-Optimal Sparse Adaptive Group Testing | ||
| Authors | Nelvin Tan, Jonathan Scarlett, National University of Singapore, Singapore | ||
| Session | G.4: Group Testing and Sparse Codes | ||
| Presentation | Lecture | ||
| Track | Graphs, Games, Sparsity, and Signal Processing | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether any defective item is present. This problem is relevant in areas such as medical testing, data science, communications, and many more. Motivated by physical considerations, we consider a sparsity-based constrained setting (Gandikota {\em et al.}, 2019), in which items are finitely divisible and thus may participate in at most $\gamma$ tests (or alternatively, each test may contain at most $\rho$ items). While information-theoretic limits and algorithms are known for the non-adaptive setting, relatively little is known in the adaptive setting. In this paper, we address this gap by providing an information-theoretic converse that holds even in the adaptive setting, as well as a near-optimal noiseless adaptive algorithm. In broad scaling regimes, our upper and lower bounds on the number of tests asymptotically match up to a factor of $e$. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
