Nonadaptive Group Testing Based on Sparse Pooling Graphs

DOI10.1109/TIT.2016.2621112MaRDI QIDQ5280850zbMATH OpenOpenAlexFDO

Authors Tadashi Wadayama

Publication date 27 July 2017

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

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

Mathematics Subject Classification ID

Fault detection; testing in circuits and networks (94C12)

Abstract: In this paper, an information theoretic analysis on non-adaptive group testing schemes based on sparse pooling graphs is presented. The binary status of the objects to be tested are modeled by i.i.d. Bernoulli random variables with probability p. An (l, r, n)-regular pooling graph is a bipartite graph with left node degree l and right node degree r, where n is the number of left nodes. Two scenarios are considered: a noiseless setting and a noisy one. The main contributions of this paper are direct part theorems that give conditions for the existence of an estimator achieving arbitrary small estimation error probability. The direct part theorems are proved by averaging an upper bound on estimation error probability of the typical set estimator over an (l,r, n)-regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime.

Recommendations

• Comments on ``Nonadaptive group testing based on sparse pooling graphs
• Non-adaptive group testing on graphs
• Non-adaptive group testing on graphs with connectivity
• Optimal non-adaptive probabilistic group testing in general sparsity regimes
• Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms
• Explicit Nonadaptive Combinatorial Group Testing Schemes
• Sparse Combinatorial Group Testing
• scientific article; zbMATH DE number 7650113
• Nonadaptive algorithms for threshold group testing
• Explicit Non-adaptive Combinatorial Group Testing Schemes

Cited in

(3)

• A recovery algorithm and pooling designs for one-stage noisy group testing under the probabilistic framework
• Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms
• Sparse Combinatorial Group Testing

This page was built for publication: Nonadaptive Group Testing Based on Sparse Pooling Graphs

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