Threshold group testing (extended abstract)

We introduce a natural generalization of the well-studied group testing problem: A test gives a positive (negative) answer if the pool contains at least u (at most l) positive elements, and an arbitrary answer if the number of positive elements is between these fixed thresholds l and u. We show that the p positive elements can be determined up to a constant number of misclassifications, bounded by the gap between the thresholds. This is in a sense the best possible result. Then we study the number of tests needed to achieve this goal if n elements are given. If the gap is zero, the complexity is, similarly to classical group testing, O(p log n) for any fixed u. For the general case we propose a two-phase strategy consisting of a Distill and a Compress phase. We obtain some tradeoffs between classification accuracy and the number of tests.(Abstract of the full paper.