Non-adaptive group testing: residuation theory and disjunct matrices
Author
Dinesen, Johan Vester
Term
4. term
Education
Publication year
2023
Abstract
Denne afhandling handler om ikke‑adaptiv gruppetestning, hvor man blander prøver og tester dem i grupper for at finde op til d positive elementer blandt i alt n elementer ved at bruge så få tests som muligt. Ikke‑adaptiv betyder, at alle tests planlægges på forhånd uden at justere efter tidligere resultater. Afhandlingen giver den nødvendige baggrund i residuationsteori for at undersøge matricer over den booleske semiring (0/1‑matricer med OR og AND som de grundlæggende operationer). Fokus er på d‑disjunkte matricer, som har den egenskab, at ingen rækkes 1’ere er helt dækket af foreningen af 1’erne i nogen d andre rækker. Denne egenskab gør det muligt at afkode testresultaterne effektivt og entydigt i ikke‑adaptiv gruppetestning. Vi præsenterer konstruktioner af sådanne matricer samt grænser for, hvad der er muligt, hvilket tilsammen viser, hvor effektivt man kan designe tests med sikker afkodning.
This thesis studies non-adaptive group testing, where samples are pooled and tested in groups to identify up to d positive items among n total items while using as few tests as possible. Non-adaptive means all tests are designed in advance, without adjusting based on earlier outcomes. The thesis introduces the required background in residuation theory to analyze matrices over the Boolean semiring (0/1 matrices with OR and AND as the basic operations). It focuses on d-disjunct matrices, which ensure that no row’s 1s are fully covered by the union of the 1s from any d other rows. This property enables efficient and unambiguous decoding of test outcomes in non-adaptive group testing. We present constructions of such matrices and bounds that clarify what is achievable, showing how efficiently tests can be designed while retaining reliable decoding.
[This summary has been rewritten with the help of AI based on the project's original abstract]
Documents