Optimal Non-Adaptive Group Testing with One-Sided Error Guarantees
Provides optimal algorithms and bounds for one-sided error group testing, addressing a gap in approximate recovery for practitioners who require either no false negatives or no false positives.
The paper studies non-adaptive group testing with one-sided error guarantees, showing that for false negatives only, an algorithm achieves the optimal threshold of two-sided approximate recovery, and for false positives only, a converse bound proves the better of two existing algorithms is optimal.
The group testing problem consists of determining a sparse subset of defective items from within a larger set of items via a series of tests, where each test outcome indicates whether at least one defective item is included in the test. We study the approximate recovery setting, where the recovery criterion of the defective set is relaxed to allow a small number of items to be misclassified. In particular, we consider one-sided approximate recovery criteria, where we allow either only false negative or only false positive misclassifications. Under false negatives only (i.e., finding a subset of defectives), we show that there exists an algorithm matching the optimal threshold of two-sided approximate recovery. Under false positives only (i.e., finding a superset of the defectives), we provide a converse bound showing that the better of two existing algorithms is optimal.