Efficiently Decodable Non-adaptive Group Testing

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 x i = 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 × 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 ( d 2 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 ( d 2 log n ) that can be decoded in time poly( d ) · t log 2 t + O ( t ). To the best of our knowledge, this is the first result that achieves an efficient decoding time and matches the best known O ( d 2 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, ℓ)- list disjunct matrices, which represent the more general “list group testing” problem whose goal is to output less than d + ℓ 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, ℓ)-sparsity separator structures [Ganguly, ISAAC 2008] and in constructing tolerant testers for Reed-Solomon codes in the data stream model.

Authors

• Piotr Indyk
• Hung Q. Ngo 0001
• Atri Rudra

Keywords

No keywords are indexed for this paper.