Date Added: Jul 2011
The authors consider the problem of detecting a small subset of defective items from a large set via non-adaptive "Random pooling" group tests. They consider both the case when the measurements are noiseless, and the case when the measurements are noisy (the outcome of each group test may be independently faulty with probability q). Order-optimal results for these scenarios are known in the literature. They give information-theoretic lower bounds on the query complexity of these problems, and provide corresponding computationally efficient algorithms that match the lower bounds up to a constant factor.