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

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.

4 pages, 1 figure

References in corpus (3)

• Performance of group testing algorithms with near-constant tests-per-item
• Group testing with Random Pools: Phase Transitions and Optimal Strategy
• The capacity of non-identical adaptive group testing

Cited by in corpus (9)

• Information-theoretic and algorithmic thresholds for group testing
• Optimal group testing
• Rates of adaptive group testing in the linear regime
• Improved bounds for noisy group testing with constant tests per item
• AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing
• Learning Erdős-Rényi Random Graphs via Edge Detecting Queries
• A negative binomial approximation in group testing
• Nearly Optimal Sparse Group Testing
• Hypothesis Test for Bounds on the Size of Random Defective Set