Nonadaptive Group Testing With Random Set of Defectives

摘要

In a group testing scheme, a series of tests are designed to identify a small number t of defective items that are present among a large number N of items. Each test takes a group of items as input and produces a binary output indicating whether any defective item is present in the group. In a non-adaptive scheme, the tests have to be designed in one-shot. In this setting, designing a testing scheme is equivalent to the construction of a disjunct matrix, an M×N binary matrix where the union of supports of any t columns does not contain the support of any other column. In principle, one wants to have such a matrix with a minimum possible number M of rows. In this paper, we consider the scenario where defective items are random and follow simple probability distributions. In particular, we consider the cases where: 1) each item can be defective independently with probability tN and 2) each t -set of items can be defective with uniform probability. In both the cases, our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before, and it is known that Θ(tlogN) tests are necessary as well as sufficient (via random coding) in both the cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on constant-weight error-correcting codes and their minimum distance. In particular, it is known that codes result in test matrices with O(t2logN) rows that identify any t defectives. We go beyond the minimum distance analysis and connect the average distance of a constant weight code to the parameters of the resulting test matrix. Indeed, we show how distance, a pairwise property of the columns of the matrix, translates to a (t+1) -wise property of the columns. With our relaxed requirements, we show that using explicit constant-weight codes (e.g., based on algebraic geometry codes) we may achieve a number of tests equal to O(t(log2N/logt)) for both the first and second cases. While only away by a factor of (logN/logt) from the optimal number of tests, this is the best set of parameters that one can obtain from a deterministic construction, and our main contribution lies in relating the group testing properties to the average and minimum distances of constant-weight codes.