Error-Correcting Group Testing and Residuation Theory on Boolean

Coding Theory and Cryptography Seminars

We present a novel approach to non-adaptive group testing by modelling it in terms of residuated pairs on partially ordered sets. The resulting efficient decision scheme covers large classes of group testing schemes for pandemic diseases during the initial low prevalence phase. Our design of the testing schemes is based on incidence matrices of finite partial linear spaces. The results may be tailored for different estimated disease prevalence levels. The key idea is that by building sufficient structure into the test-design matrix, one may increase what could be called the efficiency of the testing. The major part of our talk deals with the error-free scenario; an adaptation to an asymmetric error situation is possible and will be dealt with in the second part. This is work in progress with my co-author Cornelia Roessing.