Group Testing Schemes From Codes and Designs

DOI10.1109/TIT.2017.2746564zbMATH Open1390.94899arXiv1510.02873OpenAlexW2963991930MaRDI QIDQ4566548FDOQ4566548

Authors: Alexander Barg, Arya Mazumdar 

Publication date: 27 June 2018

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In group testing, simple binary-output tests are designed to identify a small number $t$ of defective items that are present in a large population of $N$ items. Each test takes as input a group of items and produces a binary output indicating whether the group is free of the defective items or contains one or more of them. In this paper we study a relaxation of the combinatorial group testing problem. A matrix is called $(t,epsilon)$-disjunct if it gives rise to a nonadaptive group testing scheme with the property of identifying a uniformly random $t$-set of defective subjects out of a population of size $N$ with false positive probability of an item at most $epsilon$. We establish a new connection between $(t,epsilon)$-disjunct matrices and error correcting codes based on the dual distance of the codes and derive estimates of the parameters of codes that give rise to such schemes. Our methods rely on the moments of the distance distribution of codes and inequalities for moments of sums of independent random variables. We also provide a new connection between group testing schemes and combinatorial designs.

Full work available at URL: https://arxiv.org/abs/1510.02873

Mathematics Subject Classification ID

Combinatorial codes (94B25)

Cited In (1)

• The design of (almost) disjunct matrices by evolutionary algorithms

This page was built for publication: Group Testing Schemes From Codes and Designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566548)