Piotr Indyk, Hung Q. Ngo and Atri Rudra

Motivated by applications in data stream algorithms, we consider the following
"efficiently decodable'' non-adaptive group testing problem. There is an
unknown string *x* in *{0,1} ^{n}* with at most

This paper presents a randomness efficient construction of
*d*-disjunct matrices (they are representations of group testing algorithms)
with *t=O(d ^{2}log n)* tests that can be decoded in time

A crucial building block in our construction is the notion of
*(d,L)-list disjunct* matrices, where the goal is to output
at most *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.

- To appear in proceedings of The 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 10). January 2010. [PDF]