Improved bounds for noisy group testing with constant tests per item

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.

References in corpus (12)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Group testing algorithms: bounds and simulations
• Group Testing: An Information Theory Perspective
• Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
• The Capacity of Adaptive Group Testing
• Evolution of scaling emergence in large-scale spatial epidemic spreading
• Performance of group testing algorithms with near-constant tests-per-item
• Individual testing is optimal for nonadaptive group testing in the linear regime
• Information-theoretic and algorithmic thresholds for group testing
• Near-Optimal Noisy Group Testing via Separate Decoding of Items
• The capacity of Bernoulli nonadaptive group testing
• Improved group testing rates with constant column weight designs

Cited by in corpus (3)

• Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing
• Noisy group testing via spatial coupling
• Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing