Group Testing with Selectable Thresholds
arXiv:2607.14448
The paper studies group testing where each pooled test can be assigned a selectable threshold, and shows how to recover the defective set efficiently, achieving near‑optimal test rates especially when thresholds are large, and provides concrete test and decoding schemes for fixed thresholds.
Abstract
We consider the problem of group testing, in which one seeks to identify a subset of defective items of size from a larger set of 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 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 ).