Performance of group testing algorithms with near-constant tests-per-item

We consider the nonadaptive group testing with N items, of which $K = Θ(N^θ)$ are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement, and place the item in those tests. We analyse the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes, and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as COMP and DD. This gives the best known nonadaptive group testing performance for $θ> 0.43$, and the best proven performance with a practical decoding algorithm for all $θ\in (0,1)$. We also give a converse result showing that the DD algorithm is optimal for these designs when $θ> 1/2$.