# ICS 269, Fall 2004: Theory Seminar

## 15 Oct 2004:

Very Efficient Non-Adaptive Group Testing

David Eppstein, Michael T. Goodrich, and Daniel S. Hirschberg

In combinatorial group testing, a set of items is given,
most of which are good (or pure) and some of which might be
defective (or contaminated).
Tests for contamination can be applied to arbitrary subsets
of these items.

We present descriptions of very efficient non-adaptive
combinatorial group testing algorithms that determine
which *d* items out of a given set of *n* items are defective
for particular small values of *d*.
These algorithms require fewer computational resources
and/or fewer combinatorial tests than previously known algorithms
for all practical values of *n*.