On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing

Huseyin A. Inan, Peter Kairouz, Mary Wootters, Ayfer Özgür

Introduction

Group testing is a fundamental problem in combinatorial search and information theory, aimed at identifying a small set of $d$ defective items within a large population of $N$ items using a minimum number of binary tests $t$. While it is well-established that $\Theta(d \log N)$ tests are necessary and sufficient, most constructions achieving this bound rely on randomized matrices. Finding "strongly explicit" deterministic constructions that are both test-efficient and computationally efficient to decode remains a significant challenge.

This paper demonstrates that the classic Kautz-Singleton (KS) construction, previously considered suboptimal for combinatorial (zero-error) group testing, is actually order-optimal for the probabilistic setting. In this regime, a vanishingly small error probability is permitted, allowing the KS construction to reach the theoretical limit of $\Theta(d \log N)$ tests.

The Kautz-Singleton Construction

The Kautz-Singleton construction builds test matrices by leveraging the properties of Reed-Solomon (RS) codes. An RS code defined over a finite field $\mathbb{F}_q$ is converted into a binary matrix through a simple mapping: each $q$-ary symbol is replaced by a "one-hot" binary vector of length $q$.

The Kautz-Singleton construction mapping a Reed-Solomon code to a binary matrix via identity mapping.

The strength of this approach lies in the algebraic structure of RS codes. Since codewords are evaluations of polynomials, the number of shared test positions between any two items is bounded by the degree of the underlying polynomials. This paper shifts the analysis from traditional combinatorial metrics like "disjunctiveness" to a direct probabilistic evaluation of the "covering" property, showing that the overlap between items is sufficiently limited to ensure high success rates.

Efficient Recursive Decoding

A major contribution of this work is a new recursive decoding algorithm. While standard "cover decoders" require time linear in the population size ($O(tN)$), the proposed method uses a stacked matrix structure to identify the index of defective items piece-by-piece. This recursive pruning reduces the search space exponentially, achieving a sub-linear decoding complexity of $O(d^3 \log N \log \log_d N)$.

Empirical Results and Practical Superiority

To validate the theoretical findings, the authors conducted synthetic simulations comparing the KS construction against standard randomized designs, such as Bernoulli matrices and near-constant column weight constructions.

Success probability comparison for $N=2000, d=100$ between the K-S construction and standard randomized designs.

As shown in the simulations for $N=2000$ and $d=100$, the KS construction (labeled "The K-S construction") consistently outperforms randomized Bernoulli designs, achieving a higher success probability for the same number of tests. This demonstrates that the algebraic structure of KS provides practical advantages over purely random pooling strategies.

Conclusion and Future Directions

This research bridges the gap between deterministic constructions and information-theoretic optimality in probabilistic group testing. By proving that the KS construction is order-optimal for $d = \Omega(\log^2 N)$, the authors provide a robust, explicit framework for efficient testing. Future research will focus on extending these results to smaller regimes of $d$ and eliminating the small $\log \log_d N$ overhead in the number of tests required for sub-linear decoding.

Summary updated

Abstract

The following topics are dealt with: optimisation; computational complexity; probability; graph theory; learning (artificial intelligence); channel coding; convex programming; channel capacity; Markov processes; stochastic processes.
BibTeX
@article{inan2019optimality,
  author = {Huseyin A. Inan and Peter Kairouz and Mary Wootters and Ayfer Özgür},
  title = {{On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=RDV07L015Z},
}
Figure