The Capacity of Bernoulli Nonadaptive Group Testing
From MaRDI portal
Publication:4566549
DOI10.1109/TIT.2017.2748564zbMATH Open1453.62382DBLPjournals/tit/Aldridge17arXiv1511.05201WikidataQ61308002 ScholiaQ61308002MaRDI QIDQ4566549FDOQ4566549
Authors: Matthew Aldridge 
Publication date: 27 June 2018
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: We consider nonadaptive group testing with Bernoulli tests, where each item is placed in each test independently with some fixed probability. We give a tight threshold on the maximum number of tests required to find the defective set under optimal Bernoulli testing. Achievability is given by a result of Scarlett and Cevher; here we give a converse bound showing that this result is best possible. Our new converse requires three parts: a typicality bound generalising the trivial counting bound, a converse on the COMP algorithm of Chan et al, and a bound on the SSS algorithm similar to that given by Aldridge, Baldassini, and Johnson. Our result has a number of important corollaries, in particular that, in denser cases, Bernoulli nonadaptive group testing is strictly worse than the best adaptive strategies.
Full work available at URL: https://arxiv.org/abs/1511.05201
Cited In (3)
This page was built for publication: The Capacity of Bernoulli Nonadaptive Group Testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566549)
