Performance of Group Testing Algorithms With Near-Constant Tests Per Item

DOI10.1109/TIT.2018.2861772MaRDI QIDQ4615335zbMATHDBLPWikidataFDO

Authors Oliver Johnson, Matthew Aldridge, Jonathan Scarlett

Publication date 28 January 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.07122

zbMATH Keywords

test designnonadaptive group testingcomparison with Bernoulli designs

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Design of statistical experiments (62K99)

Abstract: We consider the nonadaptive group testing with N items, of which $K=Theta(N^{h}eta)$ 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 $heta>0.43$, and the best proven performance with a practical decoding algorithm for all $hetain(0,1)$. We also give a converse result showing that the DD algorithm is optimal for these designs when $heta>1/2$.

Recommendations

• Group Testing Algorithms: Bounds and Simulations
• Improved Bounds for Noisy Group Testing With Constant Tests per Item
• A class of asymptotically optimal group testing strategies to identify good items
• An improved algorithm for quantitative group testing
• Efficient group testing algorithms with a constrained number of positive responses
• On optimal nested group testing algorithms
• Group Testing With Probabilistic Tests: Theory, Design and Application
• Efficient Algorithms for Noisy Group Testing
• An efficient algorithm for combinatorial group testing

Cited in

(5)

• Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing
• Generalized framework for group testing: queries, feedbacks and adversaries
• scientific article; zbMATH DE number 7758315 (Why is no real title available?)
• Optimal group testing
• Information-theoretic and algorithmic thresholds for group testing

This page was built for publication: Performance of Group Testing Algorithms With Near-Constant Tests Per Item

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4615335)