Group Testing with Selectable Thresholds
For researchers in group testing, this work provides a new threshold model that bridges gap between combinatorial and probabilistic approaches, with theoretical guarantees for both asymptotic and finite regimes.
This paper introduces a group testing model with selectable thresholds, achieving near-optimal recovery rates approaching the information-theoretic limit of 1 in the large-threshold regime, and matching upper and lower bounds on the number of tests in the fixed-threshold dense limit.
We consider the problem of group testing, in which one seeks to identify a subset of defective items of size $k$ from a larger set of $n$ items based on pooled tests. We introduce a selectable threshold model, in which each test has an associated threshold that can be chosen, such that the test outcome is 1 if and only if the number of defectives in the test is no smaller than that threshold. In settings with a large or unbounded maximum threshold, we establish conditions under which high-probability recovery can be attained with a rate (i.e., the asymptotic ratio of $\log_2{n \choose k}$ to the number of tests) approaching its maximum possible value of 1. Moreover, in the case of a fixed maximum threshold, we establish an achievable number of tests using simple and computationally efficient decoding methods, and a converse that holds under suitable regularity conditions on the test design, with the two coinciding in the dense limit (i.e., $θ$ approaching one in the scaling $k = Θ(n^θ)$).