An Overview of Algorithms and Theory for Group Testing
COM1 Level 3
MR1, COM1-03-19
Abstract:
The group testing problem concerns discovering a small number of “defective items” (or “infected individuals”) within a large population by performing tests on pools of items.A test is positive if the pool contains at least one defective, and negative if it contains no defectives. This is a sparse inference problem with a combinatorial flavour, with applications in medical testing, biology, multi-access communication, database systems, and more.
I will review recent advances in algorithms and theory for group testing, including both information-theoretic limits and performance bounds for practical algorithms, with an emphasis on the following defining features:
•Non-adaptive testing (all tests must be designed in advance) vs. adaptive testing (tests are designed sequentially based on previous outcomes)
•Noiseless testing (tests are perfectly reliable) vs. noisy tests (some test outcomes are corrupted)
This talk is loosely based on a survey monograph available athttps://arxiv.org/abs/1902.06002, as well as some more recent developments that followed it.
Bio:
Jonathan Scarlett is an Associate Professor in the Department of Computer Science and Department of Mathematics, National University of Singapore. His research interests are in the areas of information theory, machine learning, and high-dimensional statistics, with a particular emphasis on information-theoretic methods/foundations for data science problems. Previously, Jonathan received the B.Eng. degree in electrical engineering and the B.Sci. degree in computer science from the University of Melbourne, Australia. Between 2011-2014 he was a Ph.D. student in the Signal Processing and Communications Group at the University of Cambridge, and between 2014-2017 he was post-doctoral researcher at LIONS, EPFL.