Non-Adaptive Randomized Algorithm for Group Testing
  We study the problem of group testing with a non-adaptive randomized
algorithm in the random incidence design (RID) model where each entry in the
test is chosen randomly independently from $\{0,1\}$ with a fixed probability
$p$.
  The property that is sufficient and necessary for a unique decoding is the
separability of the tests, but unfortunately no linear time algorithm is known
for such tests. In order to achieve linear-time decodable tests, the algorithms
in the literature use the disjunction property that gives almost optimal number
of tests.
  We define a new property for the tests which we call semi-disjunction
property. We show that there is a linear time decoding for such test and for
$d\to \infty$ the number of tests converges to the number of tests with the
separability property and is therefore optimal (in the RID model). Our analysis
shows that, in the RID model, the number of tests in our algorithm is better
than the one with the disjunction property even for small $d$.
