Group-testing refers to the problem of identifying (with high probability) a (small) subset of D defectives from a (large) set of N items via a "small" number of "pooled" tests (i.e., tests have a positive outcome if even one of the items being tested in the pool is defective, else they have a negative outcome). For ease of presentation in this work we focus the regime when the number of defectives is sublinear, i.e., D = O N 1−δ for some δ > 0. The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of literature demonstrates that Θ(D log(N )) tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexity that is sub-linear in N have started being investigated (recent work by [1], [2], [3] gave some of the first such algorithms). In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity (O (D log(N )) in both the performance metrics). The total number of stages of our adaptive algorithm is "small" (O (log(D))). Similarly, in the scenario with non-adaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires O (D log(D) log(N )) tests and has a decoding complexity of O(D(log N + log 2 D)). Finally, we present an adaptive algorithm that only requires 2 stages, and for which both the number of tests and the decoding complexity scale as O(D(log N + log 2 D)). For all three settings the probability of error of our algorithms scales as O (1/(poly(D)). 2 A slightly more involved information-theoretic argument is required if the group-testing procedure is allowed to fail with "small" probability. However, even in this setting, essentially the same lower bounds can be proven (up to small constant multiplicative factors that may depend on the allowed probability of error) -e.g., [13] , [14] . 3 Another flavour we do not focus on in this work corresponds to whether the design of the testing procedure is deterministic or randomized. Recent works -for instance [15] , [16] -provide computationally efficient deterministic designs. In this work, however, we focus on "Monte Carlo" type randomized design algorithms.
Cai et al. REF propose Grotesque for non-adaptive group testing and adaptive group testing.
GROTESQUE: Noisy Group Testing (Quick and Efficient)
2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)
2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)
Mathematics Computer Science