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 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.
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