Overview
Research was conducted into the Threshold Group Testing (TGT) problem within a noiseless and non-adaptive experimental framework. The primary objective was to precisely recover a sparse binary vector using the minimum possible number of pooled tests. In the TGT methodology, a test applied to a subset of items yields a positive outcome if the quantity of defective items (represented as 1's) within that subset equals or exceeds a predefined threshold. Conversely, a negative outcome is registered if this threshold is not met.
The investigation aimed to compare the complexity of TGT against Classical Group Testing (CGT), which is defined as the specific instance of TGT where the threshold value is set to one. A central focus was to analyze how increasing this threshold impacts the requisite number of tests for accurate recovery.
Approach
The study derived a sharp information-theoretic phase transition for TGT. This derivation focused on the constant-column test design, providing an expression for the required number of tests: $c_{\mathrm{inf}}^{\mathrm{TGT}}k\log(n/k)$. The constant $c_{\mathrm{inf}}^{\mathrm{TGT}}$ was articulated as a function dependent on the prevalence of defective items and the specific threshold value. The derivation of the upper bound for this phase transition was contingent upon an analytic assumption. This assumption was verified to be satisfied for a threshold value of two.
Findings
- A sharp information-theoretic phase transition was derived for Threshold Group Testing (TGT) in the noiseless and non-adaptive setting, specific to the constant-column test design. The number of tests required is given by $c_{\mathrm{inf}}^{\mathrm{TGT}}k\log(n/k)$.
- The threshold constant $c_{\mathrm{inf}}^{\mathrm{TGT}}$ is a function of the prevalence of defectives and the threshold value.
- The derived upper bound for the number of tests is based on an analytic assumption, which was verified to be satisfied when the threshold value is 2.
- Analysis of $c_{\mathrm{inf}}^{\mathrm{TGT}}$ indicates that TGT, when employing the constant-column design, exhibits an information-theoretic behavior consistent with Classical Group Testing (CGT) in scenarios characterized by low prevalence of defective items.
- At higher prevalences of defective items, the threshold mechanism within TGT leads to a significant reduction in the number of required tests compared to CGT.
- Conversely, evidence suggests that when the asymptotic proportion of defective items is positive, TGT can become strictly harder than CGT, excluding trivial reductions.
Why This Matters
Understanding the information-theoretic complexity of Threshold Group Testing provides insights into the fundamental limits of sparse binary vector recovery under specific testing constraints. The identified phase transitions and the conditions under which TGT offers reductions or increases in test complexity relative to Classical Group Testing contribute to the theoretical foundations of efficient testing strategies.