Technical Program

Paper Detail

Paper IDG.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

IEEE ISIT 2021

2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!