Ahstract-The group testing problem is to identify a popu lation of K defective items from a set of n items by pooling groups of items. The result of a test for a group of items is positive if any of the items in the group is defective and negative otherwise. The goal is to judiciously group subsets of items such that defective items can be reliably recovered using the minimum number of tests, while also having a low complexity decoder. We describe SAFFRON (Sparse-grAph codes Framework For gROup testiNg), a non-adaptive group testing scheme that recovers at least a (1 -E)-fraction (for any arbitrarily small E > 0) of K defective items with high probability with m = 6C ( E) K log2 n tests, where C (E) is a precisely characterized constant that depends only on E. For instance, it can provably recover at least (1 -lO-G)K defective items with m r--' 68K log2 n tests. The computational complexity of the decoding algorithm is O(Klogn), which is order optimal. Further, we describe a systematic methodology to robustify SAFFRON such that it can reliably recover the set of K defective items even in the presence of erroneous or noisy test results. We also propose Singleton-Only-SAFFRON, a variant of SAFFRON, that recovers all the K defective items with m = 2e(1 + a)K log K log2 n tests with probability 1 -0 ( �" ) , where a > 0 is a constant. Our key intellectual contribution involves the pioneering use of powerful density evolution methods of modern coding theory (e.g. sparse-graph codes) for efficient group testing design and performance analysis.
Another framework where the goal is to recover at least a (1 − )-fraction (for any arbitrarily small > 0) of the defective set with high probability was studied in REF where the authors provided a scheme with order-optimal O(d log N ) tests and the computational complexity.
SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes
2016 IEEE International Symposium on Information Theory (ISIT)
2016 IEEE International Symposium on Information Theory (ISIT)
Computer Science Mathematics