Paper Info
Title
On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing.
Abstract
We consider the probabilistic group testing problem where d random defective items in a large population of N items are identified with high probability by applying binary tests. It is known that $\Theta(d\log N)$ tests are necessary and sufficient to recover the defective set with vanishing probability of error. However, to the best of our knowledge, there is no explicit (deterministic) construction achieving $\Theta(d\log N)$ tests in general. In this work, we show that a famous construction introduced by Kautz and Singleton for the combinatorial group testing problem (which is known to be suboptimal for combinatorial group testing for moderate values of d) achieves the order optimal $\Theta(d\log N)$ tests in the probabilistic group testing problem. This provides the first strongly explicit construction achieving the order optimal result in the probabilistic group testing setting. To prove the order-optimality of Kautz and Singleton’s construction in the probabilistic setting, we provide a novel analysis of the probability of a non-defective item being covered by a random defective set directly, rather than arguing from combinatorial properties of the underlying code, which has been the main approach in the literature. Furthermore, we use a recursive technique to convert this construction into one that can also be efficiently decoded with only a log-log factor increase in the number of tests.
Year
DOI
Venue
2018
10.1109/TIT.2019.2902397
2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
Keywords
DocType
Volume
Testing,Decoding,Probabilistic logic,Noise measurement,Complexity theory,Atmospheric measurements,Particle measurements
Conference
abs/1808.01457
Issue
ISSN
Citations 
9
0018-9448
4
PageRank 
References 
Authors
0.40
24
4
Name
Order
Citations
PageRank
Huseyin A. Inan1367.57
Peter Kairouz218922.27
Mary Wootters317225.99
Ayfer Özgür474867.16