Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms

Oliver Gebhard, Max Hahn-Klimroth, Olaf Parczyk, Manuel Penschuck, Maurice Rolvien, Jonathan Scarlett, Nelvin Tan

Abstract

Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^\theta$ (with $\theta \in (0,1)$), with $n$ individuals among which $k$ are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number $\Delta$ of tests an individual can be placed in, or the maximum number $\Gamma$ of individuals in a given test. In this paper, we substantially or completely close several of the most prominent gaps. In the case of $\Delta$-divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of $e$ more generally. In the case of $\Gamma$-sized tests, we provide a comprehensive analysis of the regime $\Gamma = \Theta(1)$, and establish a precise threshold proving the asymptotic optimality of SCOMP equipped with a tailored pooling scheme. Finally, we provide near-optimal adaptive algorithms and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.

Introduction

Group testing is the process of identifying a small number of "infected" items ($k$) out of a large population ($n$) by pooling samples into a smaller number of tests ($m$). While the theoretical limits for unconstrained group testing are well-understood, real-world applications face two major hurdles:

  1. $\Delta$-divisibility: An individual's sample volume may be limited, restricting them to at most $\Delta$ tests.
  2. $\Gamma$-sized tests: To avoid dilution effects, each test can contain at most $\Gamma$ individuals.

This paper aims to tighten the bounds for these scenarios and identify the most efficient algorithms for constrained environments.

Methods and Algorithms

The authors employ a mix of probabilistic analysis and algorithmic refinement. For non-adaptive testing, they utilize Random Regular Designs and the Configuration Model. They focus on two main recovery algorithms:

  • Definite Defectives (DD): A logic-based approach that identifies uninfected items first.
  • SCOMP (Sequential Combinatorial Orthogonal Matching Pursuit): A refinement of DD that uses a greedy approach to explain all positive test results.

For adaptive testing, they develop a Sequential Splitting algorithm tailored to respect the $\Delta$ and $\Gamma$ constraints.

Key Results: $\Delta$-divisible Items

For items limited to $\Delta$ tests, the authors tightened the required number of tests to $m \approx \Delta k \cdot \max \{ e^{-1} k^{(1-\theta)/(\Delta\theta)}, k^{1/\Delta} \}$. A striking finding is that the simple DD algorithm is asymptotically optimal when the infection density is high ($\theta > 1/2$).

Theoretical bounds for Δ-divisible items showing the adaptivity gap.

Crucially, this work proves an "adaptivity gap": while adaptivity offers little benefit in unconstrained group testing, it significantly reduces the number of tests needed under $\Delta$-divisibility constraints.

Key Results: $\Gamma$-sized Tests

For tests limited to a constant size $\Gamma$, the paper establishes a precise recovery threshold: $m \approx \max \{ (1 + \frac{\theta}{1-\theta})\frac{n}{\Gamma}, \frac{2n}{\Gamma+1} \}$. In sparse regimes ($\theta < 1/2$), the more sophisticated SCOMP algorithm is required to reach the optimal threshold.

Performance thresholds for Γ-sized tests showing algorithm optimality.

Conclusion

By strengthening both achievability and converse bounds, this research provides a near-complete picture of the limits of sparsity-constrained group testing. The results demonstrate that simple logic-based algorithms can be remarkably effective, provided the pooling scheme is correctly designed to respect physical constraints. Future work will look to extend these results to noisy testing environments.

Summary updated

Abstract

Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k = n^{\theta }$ (with $\theta \in (0,1)$ ), with $n$ individuals among which $k$ are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number $\Delta $ of tests an individual can be placed in, or the maximum number $\Gamma $ of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of $\Delta $ -divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of $\Gamma $ -sized tests, we provide a comprehensive analysis of the regime $\Gamma = \Theta (1)$ , and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.
BibTeX
@article{gebhard2020near,
  author = {Oliver Gebhard and Max Hahn-Klimroth and Olaf Parczyk and Manuel Penschuck and Maurice Rolvien and Jonathan Scarlett and Nelvin Tan},
  title = {{Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  doi = {10.48550/arxiv.2004.11860},
}
Figure