SAFFRON

SAFFRON: a fast, efficient, and robust framework for group testing based on sparse-graph codes. Group testing is the problem of identifying K defective items among n items by pooling groups of items. In this paper, we design group testing algorithms for approximate recovery with order-optimal sample complexity by leveraging design and analysis tools from modern sparse-graph coding theory. Our algorithm, SAFFRON, recovers at least (1 - ε)K defective items w.p.1 - K/nr with m = 2(1 + r)C(ε)K log 2 n tests, where ε is an arbitrarily small constant, C(ε) is a precisely characterizable constant, and r is any positive integer. The decoding complexity is Θ(K log n). We also propose variations of SAFFRON, which are robust to noise and unknown offsets. For example, for n ≃ 4.3 × 10 9 and K = 128, our algorithm is observed to recover all defective items with m ≃ 8.3 × 10 5 tests, even in the presence of noisy test results. Moreover, the decoding time takes less than 4 seconds on a laptop with a 2 GHz Intel Core i7 and 8 GB memory.