Efficient Designs for Threshold Group Testing Without Gap

Thach V. Bui, Yeow Meng Chee, Van Khu Vu

Introduction

Group testing is a combinatorial technique used to identify a small subset of "defective" items within a large population by testing pools of items rather than individuals. While Standard Group Testing (SGT) identifies a pool as positive if at least one defective item is present, Threshold Group Testing (TGT) introduces a more complex requirement: a test is positive only if the number of defective items in the pool reaches or exceeds a specific threshold $u$.

This paper addresses the "without gap" model of TGT, where a test is strictly positive if there are $\ge u$ defectives and negative if there are $\le u-1$. While TGT is highly relevant for biological and chemical assays where a minimum concentration is required for detection, previous non-adaptive designs—where all tests are determined before any results are known—suffered from prohibitive decoding complexities. This research presents the first deterministic, non-adaptive TGT designs where decoding time scales polynomially with the number of defectives and the threshold, rather than exponentially.

The Computational Bottleneck in TGT

In the context of large-scale screening, the efficiency of a group testing scheme is measured by two primary factors: the number of tests required and the time it takes to decode the results. For TGT without gap, existing methods were often impractical for large populations ($n$) or high numbers of defectives ($d$). Previous decoding algorithms typically scaled exponentially ($2^d$) or relative to the population size raised to the threshold power ($n^u$).

Earlier attempts to simplify the problem often relied on an "auxiliary set"—a known set of $u-1$ defectives used as a baseline. However, in a non-adaptive setting, identifying such a set beforehand is a logical impossibility. This paper overcomes this "catch-22" by introducing a novel combinatorial structure that does not require prior knowledge of any defective items.

Methodology: Single Selectors and Exclusion Operators

The authors' breakthrough relies on two primary innovations in measurement matrix design and algorithmic decoding:

1. Single Selectors

The authors define and prove the existence of $(m, d, n)$-single selectors. These are Boolean matrices designed such that for any subset of $d$ defectives, there exists at least one row in the matrix that contains exactly $m$ of those defectives. By setting $m=u$, the design ensures that the system can "hit" the threshold $u$ precisely, allowing the decoder to isolate specific groups of defectives.

2. The Exclusion Operator ($\circ$)

To process the results of these single selectors, the authors introduce a new matrix operation that combines single selectors with disjunct matrices (a staple of standard group testing). This exclusion-based strategy allows the decoder to identify a subset of defectives and then "subtract" them from the pool. By effectively reducing a complex threshold problem into a series of simpler standard group testing problems, the algorithm can identify all defectives without an exhaustive search.

3. Non-adaptive and 2-Stage Designs

The paper details both strictly non-adaptive designs (a single round of parallel tests) and 2-stage designs (where a second round of tests is informed by the first). The 2-stage approach further optimizes the number of tests required while maintaining efficient decoding.

Key Results and Complexity Analysis

The most significant contribution of this work is the transition from exponential to polynomial decoding complexity. The authors establish that for $(n, d, u)$-TGT, the decoding time is now a polynomial function of $\min\{u^u, (d-u)^{d-u}\}, d,$ and $\log n$.

Specific achievements include:

  • Constant Thresholds: When the threshold $u$ is constant, the design requires $O(d^3 \log^2 n \log(n/d))$ tests with a similarly efficient decoding time.
  • Threshold $u=2$: For this specific case, the authors achieved a non-adaptive design with $O(d^3 \log n \log(n/d))$ tests and a 2-stage design requiring only $O(d^2 \log^2(n/d))$ tests.
  • Deterministic Superiority: This work represents the first instance in information theory literature where polynomial decoding complexity is achieved for TGT without gap under a deterministic, combinatorial framework.

Implications and Future Work

Beyond the immediate applications in biological screening, the authors suggest that these efficient designs may have broader implications in learning theory, specifically regarding "hidden graph" problems.

Future research directions include extending these efficient designs to the "with gap" model—where test results are arbitrary when the number of defectives falls between a lower bound $\ell$ and an upper threshold $u$. Additionally, there remains an open challenge to further minimize the number of tests to reach the information-theoretic lower bounds while preserving polynomial decoding speed.

Summary updated

BibTeX
@inproceedings{bui2024efficient,
  author = {Thach V. Bui and Yeow Meng Chee and Van Khu Vu},
  title = {{Efficient Designs for Threshold Group Testing Without Gap}},
  booktitle = {ISIT},
  year = {2024},
  doi = {10.1109/isit57864.2024.10619476},
}
Figure