The problem of group testing entails inferring a subset of defective items from a (much larger) population, using as few 'pooled tests' as possible. Each pooled test specifies a subset of the items and produces a binary outcome: 'negative' if all the items selected in the test are non-defective, and 'positive' otherwise. While the original motivation for group testing was medical testing, it has since found application across a wide variety of scenarios including wireless communications, DNA sequencing, neighbour discovery, and network tomography. We review some of the main results in group testing and then introduce a new variation of the problem ('cascaded group testing') where each test is specified by an ordered subset of items, and returns the first defective item in the specified order.
Nikhil Karamchandani is an Associate Professor with the Department of Electrical Engineering, IIT Bombay. He received the Ph.D. degree from the Department of Electrical and Computer Engineering, University of California at San Diego. He was a postdoctoral scholar with the University of California at Los Angeles and the Information Theory and Applications (ITA) Center, University of California at San Diego. His research interests include networks, information and coding theory, and statistical learning.