We consider the nonadaptive group testing with @math items, of which @math are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick @math tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23 fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for @math and the best proven performance with a practical decoding algorithm for all @math . We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when @math . We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.
Group-testing refers to the problem of identifying (with high probability) a (small) subset of @math defectives from a (large) set of @math items via a “small” number of “pooled” tests (i.e., tests that have a positive outcome if at least one of the items being tested in the pool is defective, else have a negative outcome). For ease of presentation in this paper, we focus on the regime when @math for some @math . 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 the literature demonstrates that @math 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 complexities that are sub-linear in @math have started being investigated. 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 ( @math in both the performance metrics). The total number of stages of our adaptive algorithm is “small” ( @math ). 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 @math tests and has a decoding complexity of @math . Finally, we present an adaptive algorithm that only requires two stages, and for which both the number of tests and the decoding complexity scale as @math . For all three settings, the probability of error of our algorithms scales as @math . For each of the statements mentioned earlier about the order of the number of measurements, decoding complexity, and probability of error, we provide explicitly computed “small” universal factors in our theorem statements. We consider the following "efficiently decodable" non-adaptive group testing problem. There is an unknown string x ∈ 0, 1 n with at most d ones in it. We are allowed to test any subset S ⊆ [n] of the indices. The answer to the test tells whether xi = 0 for all i ∈ S or not. The objective is to design as few tests as possible (say, t tests) such that x can be identified as fast as possible (say, poly(t)-time). Efficiently decodable non-adaptive group testing has applications in many areas, including data stream algorithms and data forensics. A non-adaptive group testing strategy can be represented by a t x n matrix, which is the stacking of all the characteristic vectors of the tests. It is well-known that if this matrix is d-disjunct, then any test outcome corresponds uniquely to an unknown input string. Furthermore, we know how to construct d-disjunct matrices with t = O(d2 log n) efficiently. However, these matrices so far only allow for a "decoding" time of O(nt), which can be exponentially larger than poly(t) for relatively small values of d. This paper presents a randomness efficient construction of d-disjunct matrices with t = O(d2 log n) that can be decoded in time poly(d) · t log2 t + O(t2). To the best of our knowledge, this is the first result that achieves an efficient decoding time and matches the best known O(d2 log n) bound on the number of tests. We also derandomize the construction, which results in a polynomial time deterministic construction of such matrices when d = O(log n log log n). A crucial building block in our construction is the notion of (d, l)-list disjunct matrices, which represent the more general "list group testing" problem whose goal is to output less than d + l positions in x, including all the (at most d) positions that have a one in them. List disjunct matrices turn out to be interesting objects in their own right and were also considered independently by [Cheraghchi, FCT 2009]. We present connections between list disjunct matrices, expanders, dispersers and disjunct matrices. List disjunct matrices have applications in constructing (d, l)-sparsity separator structures [Ganguly, ISAAC 2008] and in constructing tolerant testers for Reed-Solomon codes in the data stream model. The group testing problem is to identify a population 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 − ϵ)-fraction (for any arbitrarily small ϵ > 0) of K defective items with high probability with m = 6C(ϵ)K log 2 n tests, where C(ϵ) is a precisely characterized constant that depends only on o. For instance, it can provably recover at least (1 − 10−6)K defective items with m ≃ 68K log 2 n tests. The computational complexity of the decoding algorithm is O(K log n), 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+α)K log K log 2 n tests with probability 1 − O(1 Kα), where α > 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. An @math m×n matrix @math A with column supports @math Si is k-separable if the disjunctions @math źiźKSi are all distinct over all sets @math K of cardinality k. While a simple counting bound shows that @math m>klog2n k rows are required for a separable matrix to exist, in fact it is necessary for m to be about a factor of k more than this. In this paper, we consider a weaker definition of almost k-separability', which requires that the disjunctions are mostly distinct'. We show using a random construction that these matrices exist with @math m=O(klogn) rows, which is optimal for @math k=O(n1-β). Further, by calculating explicit constants, we show how almost separable matrices give new bounds on the rate of nonadaptive group testing.