SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes

摘要: The group testing problem is to identify a population of K defective items from set n by pooling groups items. result test for positive if any the in and negative otherwise. goal judiciously subsets such that can be reliably recovered using minimum number tests, while also having low-complexity decoder. We describe SAFFRON (Sparse-grAph codes Framework For gROup testiNg), non-adaptive scheme recovers at least (1 − ϵ)-fraction (for arbitrarily small ϵ > 0) with high probability m = 6C(ϵ)K log 2 where C(ϵ) precisely characterized constant depends only on o. instance, it provably recover 10−6)K ≃ 68K tests. computational complexity decoding algorithm O(K n), which order-optimal. Further, we systematic methodology robustify even presence erroneous or noisy results. propose Singleton-Only-SAFFRON, variant SAFFRON, all 2e(1+α)K tests 1 O(1/Kα), α 0 constant. Our key intellectual contribution involves pioneering use powerful density-evolution methods modern coding theory (e.g. sparse-graph codes) efficient design performance analysis.