Technical Program

Paper Detail

Paper IDA.3.4
Paper Title Optimal Multistage Group Testing Algorithm for 3 Defectives
Authors Ilya Vorobyev, Skolkovo Institute of Science and Technology, Russia
Session A.3: Combinatorics and Information Theory
Presentation Lecture
Track Algebraic and Combinatorial Coding Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Group testing is a well-known search problem that consists in detecting of $s$ defective members of a set of $t$ samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, a multistage group testing problem is considered. Our goal is to construct a multistage search procedure, having asymptotically the same number of tests as the optimal adaptive algorithm. We propose a new approach to designing multistage algorithms, which allows us to construct a 5-stage algorithm for finding 3 defectives with the optimal number $3\log_2t(1+o(1))$ of tests.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!