Improved constructions for non-adaptive threshold group testing

DOI10.1007/978-3-642-14165-2_47zbMATH Open1311.68186arXiv1002.2244OpenAlexW2570531678MaRDI QIDQ378256FDOQ378256

Authors: Mahdi Cheraghchi 

Publication date: 11 November 2013

Published in: Algorithmica, Automata, Languages and Programming (Search for Journal in Brave)

Abstract: The basic goal in combinatorial group testing is to identify a set of up to $d$ defective items within a large population of size $nggd$ using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool reaches a fixed threshold $u>0$, negative if this number is no more than a fixed lower threshold $ell<u$, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, $O(d^{g+2}(logd)log(n/d))$ measurements (where $g:=u-ell-1$ and $u$ is any fixed constant) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known (non-constructive) upper bound $O(d^{u+1}log(n/d))$. Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by $O(d^{g+3}(logd)logn)$. Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with $O(d^{g+3}(logd)qpoly(logn))$ and $$ measurements, for arbitrary constant $$.

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

Recommendations

• Improved constructions for non-adaptive threshold group testing
• Subquadratic non-adaptive threshold group testing
• Nonadaptive algorithms for threshold group testing
• Subquadratic non-adaptive threshold group testing
• Threshold Group Testing

zbMATH Keywords

combinatorial designsexplicit constructionslossless expandersthreshold group testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Other designs, configurations (05B30) Reliability, testing and fault tolerance of networks and computer systems (68M15) Fault detection; testing in circuits and networks (94C12)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• New constructions of superimposed codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonrandom binary superimposed codes
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Families of finite sets in which no intersection of \(\ell\) sets is covered by the union of \(s\) others
• Introduction to Coding Theory
• On the upper bound of the size of the \(r\)-cover-free families
• Born again group testing: Multiaccess communications
• Constructing small-bias sets from algebraic-geometric codes
• A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
• Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound
• Title not available (Why is that?)
• Threshold Group Testing
• k-Mismatch with Don’t Cares
• Explicit Non-adaptive Combinatorial Group Testing Schemes
• Title not available (Why is that?)
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
• On optimal superimposed codes
• Nonadaptive algorithms for threshold group testing
• Probabilistic nonadaptive group testing in the presence of errors and DNA library screening
• Generalized cover-free families.
• Some new bounds for cover-free families
• Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs
• An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution
• On error-tolerant DNA screening
• Noise-Resilient Group Testing: Limitations and Constructions
• Title not available (Why is that?)
• Randomness conductors and constant-degree lossless expanders
• Combinatorial Algorithms for Compressed Sensing
• Improved constructions for non-adaptive threshold group testing
• An upper bound of the number of tests in pooling designs for the error-tolerant complex model

Cited In (10)

• Nonadaptive algorithms for threshold group testing
• Threshold group testing with consecutive positives
• Superimposed codes and threshold group testing
• Explicit Non-adaptive Combinatorial Group Testing Schemes
• Exact learning from an honest teacher that answers membership queries
• Subquadratic non-adaptive threshold group testing
• Threshold and Majority Group Testing
• Noise-resilient group testing: limitations and constructions
• Group Testing with Multiple Mutually-Obscuring Positives
• Improved constructions for non-adaptive threshold group testing

This page was built for publication: Improved constructions for non-adaptive threshold group testing

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