Non-adaptive group testing: residuation theory and disjunct matrices

Studenteropgave: Kandidatspeciale og HD afgangsprojekt

  • Johan Vester Dinesen
4. semester, Matematik, Kandidat (Kandidatuddannelse)
This thesis presents non-adaptive group testing, which is the problem of pooling samples in tests, such that given d positive items out of n total items one minimises the amount of tests used while determining the d items of interest.

The thesis introduces the necessary background knowledge in residuation theory in order to determine properties of matrices over the Boolean semiring, specifically d-disjunct matrices, where the union of supports of any d rows does not contain the support of any other row.

Disjunct matrices provides schemes with efficient decoding for the implementation of non-adaptive group testing, and as such, we present constructions and bounds on such matrices.
ID: 532692765