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

DOI10.1109/TIT.2018.2861772zbMATH Open1428.62100DBLPjournals/tit/JohnsonAS19arXiv1612.07122WikidataQ60522077 ScholiaQ60522077MaRDI QIDQ4615335FDOQ4615335

Authors: Oliver Johnson, Matthew Aldridge, Jonathan Scarlett 

Publication date: 28 January 2019

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

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$.

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

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

zbMATH Keywords

test designnonadaptive group testingcomparison with Bernoulli designs

Mathematics Subject Classification ID

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

Cited In (5)

• Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing
• Title not available (Why is that?)
• Optimal group testing
• Generalized framework for group testing: queries, feedbacks and adversaries
• Title not available (Why is that?)

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)