Improved Constructions for Non-adaptive Threshold Group Testing. Cheraghchi, M. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), pages 552–564, 2010. Extended version in Algorithmica.Link Slides Paper doi abstract bibtex The basic goal in combinatorial group testing is to identify a set of up to $d$ defective items within a large population of size $n ≫ d$ 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} (łog d) łog(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} łog(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} (łog d) łog n)$. Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with $O(d^{g+3} (łog d) \mathrm{quasipoly}(łog n))$ and $O(d^{g+3+β} \mathrm{poly}(łog n))$ measurements, for arbitrary constant $β > 0$.
@INPROCEEDINGS{ref:conf:Che10:threshold,
author = {Cheraghchi, Mahdi},
title = {Improved Constructions for Non-adaptive Threshold
Group Testing},
booktitle = "Proceedings of the 37th {International Colloquium on
Automata, Languages and Programming (ICALP)}",
year = 2010,
pages = "552--564",
url_Link =
{https://link.springer.com/chapter/10.1007/978-3-642-14165-2_47},
url_Slides = {http://www.ima.umn.edu/videos/?id=1803},
doi = {10.1007/978-3-642-14165-2_47},
keywords = {Threshold group testing, Lossless expanders,
Combinatorial designs, Explicit constructions},
note = {Extended version in {Algorithmica.}},
url_Paper = {https://arxiv.org/abs/1002.2244},
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 $n \gg d$ 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} (\log d) \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} (\log d) \log n)$.
Using state-of-the-art constructions of lossless
condensers, however, we obtain explicit testing
schemes with $O(d^{g+3} (\log d)
\mathrm{quasipoly}(\log n))$ and $O(d^{g+3+\beta}
\mathrm{poly}(\log n))$ measurements, for arbitrary
constant $\beta > 0$.}
}
Downloads: 0
{"_id":"XEga3FKHi5oJ4CKka","bibbaseid":"cheraghchi-improvedconstructionsfornonadaptivethresholdgrouptesting-2010","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Cheraghchi"],"firstnames":["Mahdi"],"suffixes":[]}],"title":"Improved Constructions for Non-adaptive Threshold Group Testing","booktitle":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)","year":"2010","pages":"552–564","url_link":"https://link.springer.com/chapter/10.1007/978-3-642-14165-2_47","url_slides":"http://www.ima.umn.edu/videos/?id=1803","doi":"10.1007/978-3-642-14165-2_47","keywords":"Threshold group testing, Lossless expanders, Combinatorial designs, Explicit constructions","note":"Extended version in Algorithmica.","url_paper":"https://arxiv.org/abs/1002.2244","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 $n ≫ d$ 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} (łog d) łog(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} łog(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} (łog d) łog n)$. Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with $O(d^{g+3} (łog d) \\mathrm{quasipoly}(łog n))$ and $O(d^{g+3+β} \\mathrm{poly}(łog n))$ measurements, for arbitrary constant $β > 0$.","bibtex":"@INPROCEEDINGS{ref:conf:Che10:threshold,\n author =\t {Cheraghchi, Mahdi},\n title =\t {Improved Constructions for Non-adaptive Threshold\n Group Testing},\n booktitle =\t \"Proceedings of the 37th {International Colloquium on\n Automata, Languages and Programming (ICALP)}\",\n year =\t 2010,\n pages =\t \"552--564\",\n url_Link =\n {https://link.springer.com/chapter/10.1007/978-3-642-14165-2_47},\n url_Slides =\t {http://www.ima.umn.edu/videos/?id=1803},\n doi =\t\t {10.1007/978-3-642-14165-2_47},\n keywords =\t {Threshold group testing, Lossless expanders,\n Combinatorial designs, Explicit constructions},\n note =\t {Extended version in {Algorithmica.}},\n url_Paper =\t {https://arxiv.org/abs/1002.2244},\n abstract =\t {The basic goal in combinatorial group testing is to\n identify a set of up to $d$ defective items within a\n large population of size $n \\gg d$ using a pooling\n strategy. Namely, the items can be grouped together\n in pools, and a single measurement would reveal\n whether there are one or more defectives in the\n pool. The threshold model is a generalization of\n this idea where a measurement returns positive if\n the number of defectives in the pool reaches a fixed\n threshold $u > 0$, negative if this number is no\n more than a fixed lower threshold $\\ell < u$, and\n may behave arbitrarily otherwise. We study\n non-adaptive threshold group testing (in a possibly\n noisy setting) and show that, for this problem,\n $O(d^{g+2} (\\log d) \\log(n/d))$ measurements (where\n $g := u-\\ell-1$ and $u$ is any fixed constant)\n suffice to identify the defectives, and also present\n almost matching lower bounds. This significantly\n improves the previously known (non-constructive)\n upper bound $O(d^{u+1} \\log(n/d))$. Moreover, we\n obtain a framework for explicit construction of\n measurement schemes using lossless condensers. The\n number of measurements resulting from this scheme is\n ideally bounded by $O(d^{g+3} (\\log d) \\log n)$.\n Using state-of-the-art constructions of lossless\n condensers, however, we obtain explicit testing\n schemes with $O(d^{g+3} (\\log d)\n \\mathrm{quasipoly}(\\log n))$ and $O(d^{g+3+\\beta}\n \\mathrm{poly}(\\log n))$ measurements, for arbitrary\n constant $\\beta > 0$.}\n}\n\n","author_short":["Cheraghchi, M."],"key":"ref:conf:Che10:threshold","id":"ref:conf:Che10:threshold","bibbaseid":"cheraghchi-improvedconstructionsfornonadaptivethresholdgrouptesting-2010","role":"author","urls":{" link":"https://link.springer.com/chapter/10.1007/978-3-642-14165-2_47"," slides":"http://www.ima.umn.edu/videos/?id=1803"," paper":"https://arxiv.org/abs/1002.2244"},"keyword":["Threshold group testing","Lossless expanders","Combinatorial designs","Explicit constructions"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T01:08:27.550Z","downloads":1,"keywords":["threshold group testing","lossless expanders","combinatorial designs","explicit constructions"],"search_terms":["improved","constructions","non","adaptive","threshold","group","testing","cheraghchi"],"title":"Improved Constructions for Non-adaptive Threshold Group Testing","year":2010,"dataSources":["YZqdBBx6FeYmvQE6D"]}