Nonadaptive group testing with random set of defectives via constant-weight codes

Arya Mazumdar

In the field of information theory, group testing is a classic problem: how can one identify a small subset of $t$ "defective" items within a large population of $N$ items using the minimum number of tests $M$? When these tests must be designed upfront without knowing the results of previous tests, the scheme is called nonadaptive. This paper, published in the IEEE Transactions on Information Theory, advances the deterministic construction of these schemes by shifting the focus from worst-case scenarios to average-case performance using constant-weight error-correcting codes.

The Challenge of Deterministic Construction

Nonadaptive group testing is mathematically equivalent to constructing a binary $M \times N$ matrix. Traditionally, researchers have sought disjunct matrices, which guarantee the identification of defectives regardless of which $t$ items are faulty. However, this "worst-case" requirement is computationally expensive, typically requiring $M = O(t^2 \log N)$ tests.

In contrast, if we assume the set of defectives is chosen randomly—either independently with probability $t/N$ or uniformly from all possible $t$-sized subsets—the theoretical lower bound for the number of tests drops significantly to $M = O(t \log N)$. While random coding arguments prove that matrices reaching this bound exist, finding explicit, deterministic constructions that approach this efficiency has remained a significant challenge. This paper addresses this gap by providing a polynomial-time construction that achieves near-optimal performance.

Methodology: Beyond Minimum Distance

The author utilizes the Kautz-Singleton construction, a well-known method that builds binary test matrices by concatenating a $q$-ary error-correcting code with unit-weight binary vectors. The primary innovation of this work lies in the analytical framework used to evaluate these codes.

1. Average Distance Analysis

Standard coding theory often focuses on the minimum distance—the smallest difference between any two codewords. However, for group testing with random defectives, the minimum distance is an overly pessimistic metric. The author demonstrates that the success of a test matrix is more closely tied to the average Hamming distance of the underlying constant-weight code.

2. Concentration Inequalities

By applying Bernstein’s inequality, the author proves that for a randomly selected set of defectives, the "overlap" (the number of shared tests) between the union of defective items and any single non-defective item is highly unlikely to result in a false positive. This probabilistic approach allows for a relaxation of the strict disjunctness property.

3. Algebraic-Geometric (AG) Codes

To optimize the parameters, the paper employs Algebraic-Geometric codes, specifically those derived from the García-Stichtenoth Tower. These codes offer better trade-offs between rate and distance than standard Reed-Solomon codes in certain regimes, enabling the construction of more efficient test matrices when the number of items $N$ is large.

Key Insights and Results

The most profound insight of the paper is the translation of a pairwise property (the distance between two columns) into a $(t+1)$-wise property (the relationship between one column and the union of $t$ others) under random conditions. By moving from "strictly disjunct" (zero error) to "almost disjunct" (error probability $\epsilon$), the required number of tests becomes nearly linear in $t$.

Key findings include: * Near-Optimal Bounds: The proposed deterministic construction requires $O(t \frac{\log^2 N}{\log t})$ tests. Specifically, the author proves the bound $O(t \frac{\ln N}{\ln t} \ln \frac{N}{\epsilon})$. * Deterministic Efficiency: Unlike existential proofs, these matrices can be constructed in polynomial time, making them suitable for practical implementation. * Refined Analysis: The results improve upon previous "weakly separated" designs by providing a finer analysis that yields better constants, particularly in regimes where $t$ is a power of $N$.

Limitations and Future Directions

While this work significantly narrows the gap between deterministic designs and theoretical limits, a small factor of $\frac{\log N}{\log t}$ remains between this construction and the absolute information-theoretic lower bound. Closing this final gap remains an open problem in the field.

Additionally, the current analysis assumes a noiseless environment where test results are perfectly accurate. In many real-world applications, such as medical screening or sensor networks, tests may return false positives or negatives. Extending this "average distance" framework to handle noisy group testing is a natural and necessary next step for future research.

Summary updated

Abstract

In a group testing scheme, a set of tests is designed to identify a small number $t$ of defective items that are present among a large number $N$ of items. Each test takes as input a group of items and produces a binary output indicating whether any defective item is present in the group. In a non-adaptive scheme designing a testing scheme is equivalent to the construction of a disjunct matrix, an $M \times N$ binary matrix where the union of supports of any $t$ columns does not contain the support of any other column. In this paper we consider the scenario where defective items are random and follow simple probability distributions. In particular we consider the cases where 1) each item can be defective independently with probability $\frac{t}{N}$ and 2) each $t$-set of items can be defective with uniform probability. In both cases our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before and it is known that $O(t\log N)$ tests are necessary as well as sufficient (via random coding) in both cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on \emph{constant-weight error-correcting codes} and their minimum distance. We go beyond the minimum distance analysis and connect the average distance of a constant weight code to the parameters of the resulting test matrix. With our relaxed requirements, we show that using explicit constant-weight codes (e.g., based on algebraic geometry codes) we may achieve a number of tests equal to $O(t \frac{\log^2 N}{ \log t})$ for both the first and the second cases.
BibTeX
@article{mazumdar2016nonadaptive,
  author = {Arya Mazumdar},
  title = {{Nonadaptive group testing with random set of defectives via constant-weight codes}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  url = {https://openreview.net/forum?id=5LWHObfydU_},
}
Figure