Improved Bounds for Noisy Group Testing With Constant Tests per Item

DOI10.1109/TIT.2021.3138489zbMATH Open1497.62021arXiv2007.01376OpenAlexW3039641817MaRDI QIDQ5088406

Author name not available (Why is that?)

Publication date: 13 July 2022

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

Abstract: The group testing problem is concerned with identifying a small set of infected individuals in a large population. At our disposal is a testing procedure that allows us to test several individuals together. In an idealized setting, a test is positive if and only if at least one infected individual is included and negative otherwise. Significant progress was made in recent years towards understanding the information-theoretic and algorithmic properties in this noiseless setting. In this paper, we consider a noisy variant of group testing where test results are flipped with certain probability, including the realistic scenario where sensitivity and specificity can take arbitrary values. Using a test design where each individual is assigned to a fixed number of tests, we derive explicit algorithmic bounds for two commonly considered inference algorithms and thereby naturally extend the results of Scarlett & Cevher (2016) and Scarlett & Johnson (2020). We provide improved performance guarantees for the efficient algorithms in these noisy group testing models -- indeed, for a large set of parameter choices the bounds provided in the paper are the strongest currently proved.

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

zbMATH Keywords

test design noisy variant of group testing

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Statistical aspects of information-theoretic topics (62B10)