2026/07/16 by Trung-Khang Tran, Daniel McMorrow, Jonathan Scarlett
#cs.IT #math.IT #math.PR
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 log2n \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θ)).