Constructions in Non-Adaptive Group Testing - Steiner Systems and Latin Squares

In group testing we have a (large) set of items -- called population -- and a small subset of 'special' elements -- branded as 'defective' items. Our job is to identify the whole set of defective items within our population. In group testing we can use tests -- we can test a subset of the populations to get the answer 'positive' if there exist a defective item in the tested subset or 'negative' otherwise. In theory the general goal of group testing is to do this with as few tests as possible, while in practice there are usually extra conditions to be met.

Our thesis explores and introduces new constructions for non-adaptive group testing, which are particularly important for the parameter range we encounter in real life problems. Our constructions take existing good test matrices (disjunct or separable matrices) to create disjunct (or separable) test matrices of larger size from them. Aside from our constructions we introduce asymptotic results and explore ways of making our construction even better via column augmentation (adding extra columns to an already good matrix).

This talk is part of Gergely Balint's thesis defense. The first hour is open to everyone.

Event Topic

Discrete Applied Math Seminar