The Capacity of Bernoulli Nonadaptive Group Testing

DOI10.1109/TIT.2017.2748564MaRDI QIDQ4566549zbMATH OpenDBLPWikidataFDO

Authors Matthew Aldridge

Publication date 27 June 2018

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

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

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Measures of information, entropy (94A17)

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.

Cited in

(3)

• Nonadaptive group testing with lies: probabilistic existence theorems
• scientific article; zbMATH DE number 7758315 (Why is no real title available?)
• Information-theoretic and algorithmic thresholds for group testing

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)