Performance of group testing algorithms with near-constant tests-per-item

Abstract

We consider the nonadaptive group testing with N items, of which $K=\Theta (N^{\theta })$ are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement, and place the item in those tests. We analyse the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes, and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as COMP and DD. This gives the best known nonadaptive group testing performance for $\theta >0.43$, and the best proven performance with a practical decoding algorithm for all $\theta \in (0,1)$. We also give a converse result showing that the DD algorithm is optimal for these designs when $\theta >1/2$.

16 pages, 2 figures. This work was presented in part at the 2016 IEEE International Symposium on Information Theory: arXiv:1602.03471

References in corpus (5)

• Improved Adaptive Group Testing Algorithms with Applications to Multiple Access Channels and Dead Sensor Diagnosis
• Group testing with Random Pools: Phase Transitions and Optimal Strategy
• The capacity of Bernoulli nonadaptive group testing
• Improved group testing rates with constant column weight designs
• On the optimality of some group testing algorithms

Cited by in corpus (11)

• Individual testing is optimal for nonadaptive group testing in the linear regime
• Information-theoretic and algorithmic thresholds for group testing
• Optimal group testing
• Improved bounds for noisy group testing with constant tests per item
• Pooled testing to isolate infected individuals
• On the All-Or-Nothing Behavior of Bernoulli Group Testing
• Model-Based and Graph-Based Priors for Group Testing
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Noisy group testing via spatial coupling
• Small error algorithms for tropical group testing
• A negative binomial approximation in group testing