An Information-Theoretic Analysis of Threshold Group Testing
Abstract
We study the Threshold Group Testing (TGT) problem in the noiseless and non-adaptive setting, where the objective is to exactly recover a sparse binary vector from pooled tests, using as few tests as possible. In TGT, each test applied to a subset of items returns a positive outcome if the number of 1's (defective items) in that subset meets or exceeds a specified threshold, and has a negative outcome otherwise. We investigate how the complexity of TGT compares to that of Classical Group Testing (CGT), corresponding to the special case of the threshold equal to one, and analyse the impact of increasing the threshold on the required number of tests. Our main contribution is the derivation of a sharp information-theoretic phase transition at cinfTGTklog(n/k) (non-adaptive) tests for TGT within the constant-column test design. The threshold constant cinfTGT is expressed as a function of the prevalence of defectives and the threshold value. Our upper bound is derived under an analytic assumption, and we verify that this assumption is satisfied for a threshold value of 2. The value of cinfTGT reveals that TGT on the constant-column design has the same information-theoretic behaviour as CGT in the low-prevalence regime. Yet, strikingly, at higher prevalences, the threshold leads to a significant reduction in the number of tests. On the other hand, we provide evidence that when the asymptotic proportion of defective items is positive, TGT actually becomes strictly harder than CGT (excluding trivial reductions).
Related
- Every group is the automorphism group of a set-theoretic solution of the Yang--Baxter equation
- A simple proof of the group-theoretic Zhang-Yeung inequality
- Measuring Learned Equivariance: An Information Theoretic Approach
- A Sample-Based Approach for Hierarchical Information-Theoretic Compression of Probabilistic Occupancy Grids
- Conditional Fisher-Information Central Limit Theorems under Log-Concavity with Information-Theoretic Consequences
BibTeX
@misc{hofstad2026informationtheoretic,
title = {{An Information-Theoretic Analysis of Threshold Group Testing}},
author = {Remco van der Hofstad and Noela Müller and Connor Riddlesden},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.11353},
eprint = {2606.11353},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.11353},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An Information-Theoretic Analysis of Threshold Group Testing
AU - Remco van der Hofstad
AU - Noela Müller
AU - Connor Riddlesden
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2606.11353
UR - https://arxiv.org/abs/2606.11353
AB - We study the Threshold Group Testing (TGT) problem in the noiseless and non-adaptive setting, where the objective is to exactly recover a sparse binary vector from pooled tests, using as few tests as possible. In TGT, each test applied to a subset of items returns a positive outcome if the number of 1's (defective items) in that subset meets or exceeds a specified threshold, and has a negative outcome otherwise. We investigate how the complexity of TGT compares to that of Classical Group Testing (CGT), corresponding to the special case of the threshold equal to one, and analyse the impact of increasing the threshold on the required number of tests. Our main contribution is the derivation of a sharp information-theoretic phase transition at c_inf^TGTklog(n/k) (non-adaptive) tests for TGT within the constant-column test design. The threshold constant c_inf^TGT is expressed as a function of the prevalence of defectives and the threshold value. Our upper bound is derived under an analytic assumption, and we verify that this assumption is satisfied for a threshold value of 2. The value of c_inf^TGT reveals that TGT on the constant-column design has the same information-theoretic behaviour as CGT in the low-prevalence regime. Yet, strikingly, at higher prevalences, the threshold leads to a significant reduction in the number of tests. On the other hand, we provide evidence that when the asymptotic proportion of defective items is positive, TGT actually becomes strictly harder than CGT (excluding trivial reductions).
ER -