2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | G.4.1 | ||
| Paper Title | Improved non-adaptive algorithms for threshold group testing with a gap | ||
| Authors | Thach V. Bui, University of Science, VNU-HCMC, Ho Chi Minh City, Vietnam, Viet Nam; Mahdi Cheraghchi, University of Michigan, Ann Arbor, MI, USA, United States; Isao Echizen, National Institute of Informatics; The University of Tokyo, Tokyo, Japan, Japan | ||
| 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 | The basic goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items ($d \ll n$). The outcome of a test on a subset of the items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell$ defective items, where $0 \leq \ell < u$, and arbitrary otherwise. There are a few reported studies on test designs and decoding algorithms for identifying defective items. Most of the approaches in previous studies have not been feasible, because their problems settings have numerous constraints or the decoding complexities of their proposed schemes are relatively large. This paper makes four contributions. The first is a corrected theorem for a non-adaptive algorithm proposed by Chen and Fu for threshold group testing. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing. Specifically, we present a better upper bound on the number of tests for disjunct matrices as compared to previous work. The last two contributions include a reduction in the number of tests and a reduction in the decoding time for deterministically identifying defective items in a noisy setting on test outcomes. A full version of this paper is accessible at: https://arxiv.org/abs/2001.01008. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
