Algorithms for Threshold Group Testing

We study the Threshold Group Testing (TGT) problem without a gap in the noiseless, non-adaptive setting, where the goal is to exactly recover a sparse binary vector from pooled test outcomes using as few tests as possible.

In TGT, a test applied to a subset of items returns a positive outcome if the number of defective items in the subset reaches a prescribed threshold, and a negative outcome otherwise.

Under the assumption of an analytic condition, TGT has been shown to undergo a sharp information-theoretic phase transition for exact recovery on the class of constant-column test designs.

In this paper, we develop an efficient inference algorithm that achieves exact recovery with high probability using the minimum number of non-adaptive tests that are needed for the constant-column design, thereby matching the information-theoretic threshold of a natural benchmark test design.

Our approach is based on a spatially coupled test design and admits a significantly simpler analysis than existing algorithms for related group testing problems.

In particular, unlike previous methods for binary group testing, our algorithm does not rely on the analysis of intricate weighted sums.

This leads to a more straightforward proof technique, while still allowing near-optimal performance guarantees.