Individual testing is optimal for nonadaptive group testing in the linear regime

2018/01/25 by Aldridge, Matthew
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)

paper · doi:10.48550/arxiv.1801.08590

Abstract

We consider nonadaptive probabilistic group testing in the linear regime, where each of n items is defective independently with probability p in (0,1), and p is a constant independent of n. We show that testing each item individually is optimal, in the sense that with fewer than n tests the error probability is bounded away from zero.

Related

• Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes
• Noisy Linear Group Testing: Exact Thresholds and Efficient Algorithms
• Probabilistic Group Testing with a Linear Number of Tests
• On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing
• Optimum Detection of Defective Elements in Non-Adaptive Group Testing