Exact Thresholds for Noisy Non-Adaptive Group Testing
FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Computer Science - Information Theory
Information Theory (cs.IT)
Probability (math.PR)
0202 electrical engineering, electronic engineering, information engineering
FOS: Mathematics
Mathematics - Statistics Theory
Statistics Theory (math.ST)
Mathematics - Probability
Computer Science - Discrete Mathematics
DOI:
10.48550/arxiv.2401.04884
Publication Date:
2025-01-01
AUTHORS (2)
ABSTRACT
SODA 2025<br/>In recent years, the mathematical limits and algorithmic bounds for probabilistic group testing have become increasingly well-understood, with exact asymptotic thresholds now being known in general scaling regimes for the noiseless setting. In the noisy setting where each test outcome is flipped with constant probability, there have been similar developments, but the overall understanding has lagged significantly behind the noiseless setting. In this paper, we substantially narrow this gap by deriving exact asymptotic thresholds for the noisy setting under two widely-studied random test designs: i.i.d. Bernoulli and near-constant tests-per-item. These thresholds are established by combining components of an existing information-theoretic threshold decoder with a novel analysis of maximum-likelihood decoding (upper bounds), and deriving a novel set of impossibility results by analyzing certain failure events for optimal maximum-likelihood decoding (lower bounds).<br/>
SUPPLEMENTAL MATERIAL
Coming soon ....
REFERENCES ()
CITATIONS ()
EXTERNAL LINKS
PlumX Metrics
RECOMMENDATIONS
FAIR ASSESSMENT
Coming soon ....
JUPYTER LAB
Coming soon ....