Efficiently Decodable Non-Adaptive Threshold Group Testing. Bui, T. V., Kuribayashi, M., Cheraghchi, M., & Echizen, I. *IEEE Transactions on Information Theory*, 65(9):5519–5528, 2019. Preliminary version in Proceedings of ISIT 2018.Link Paper doi abstract bibtex 1 download We consider non-adaptive threshold group testing for identification of up to $d$ defective items in a set of $n$ items, where a test is positive if it contains at least $2 ≤ u ≤ d$ defective items, and negative otherwise. The defective items can be identified using $t = O ( ( \frac{d}{u} )^u ( \frac{d}{d - u} )^{d-u} (u łog{\frac{d}{u}} + łog{\frac{1}{ε}} ) · d^2 łog{n} )$ tests with probability at least $1 - ε$ for any $ε > 0$ or $t = O ( ( \frac{d}{u} )^u ( \frac{d}{d -u} )^{d - u} d^3 łog{n} · łog{\frac{n}{d}} )$ tests with probability 1. The decoding time is $t × \mathrm{poly}(d^2 łog{n})$. This result significantly improves the best known results for decoding non-adaptive threshold group testing: $O(nłog{n} + n łog{\frac{1}{ε}})$ for probabilistic decoding, where $ε > 0$, and $O(n^u łog{n})$ for deterministic decoding.

@ARTICLE{ref:BKCE19,
author = {Thach V. Bui and Minoru Kuribayashi and Mahdi
Cheraghchi and Isao Echizen},
title = {Efficiently Decodable Non-Adaptive Threshold Group
Testing},
year = 2019,
journal = {{IEEE Transactions on Information Theory}},
volume = 65,
number = 9,
pages = {5519--5528},
note = {Preliminary version in Proceedings of {ISIT 2018}.},
doi = {10.1109/TIT.2019.2907990},
url_Link = {https://ieeexplore.ieee.org/document/8676252},
url_Paper = {https://arxiv.org/abs/1712.07509},
abstract = {We consider non-adaptive threshold group testing for
identification of up to $d$ defective items in a set
of $n$ items, where a test is positive if it
contains at least $2 \leq u \leq d$ defective items,
and negative otherwise. The defective items can be
identified using $t = O ( ( \frac{d}{u} )^u (
\frac{d}{d - u} )^{d-u} (u \log{\frac{d}{u}} +
\log{\frac{1}{\epsilon}} ) \cdot d^2 \log{n} )$
tests with probability at least $1 - \epsilon$ for
any $\epsilon > 0$ or $t = O ( ( \frac{d}{u} )^u (
\frac{d}{d -u} )^{d - u} d^3 \log{n} \cdot
\log{\frac{n}{d}} )$ tests with probability 1. The
decoding time is $t \times \mathrm{poly}(d^2
\log{n})$. This result significantly improves the
best known results for decoding non-adaptive
threshold group testing: $O(n\log{n} + n
\log{\frac{1}{\epsilon}})$ for probabilistic
decoding, where $\epsilon > 0$, and $O(n^u \log{n})$
for deterministic decoding. }
}

Downloads: 1

{"_id":"wSRGYbQimkKj5juAH","bibbaseid":"bui-kuribayashi-cheraghchi-echizen-efficientlydecodablenonadaptivethresholdgrouptesting-2019","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":["Bui, T. V.","Kuribayashi, M.","Cheraghchi, M.","Echizen, I."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Thach","V."],"propositions":[],"lastnames":["Bui"],"suffixes":[]},{"firstnames":["Minoru"],"propositions":[],"lastnames":["Kuribayashi"],"suffixes":[]},{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Isao"],"propositions":[],"lastnames":["Echizen"],"suffixes":[]}],"title":"Efficiently Decodable Non-Adaptive Threshold Group Testing","year":"2019","journal":"IEEE Transactions on Information Theory","volume":"65","number":"9","pages":"5519–5528","note":"Preliminary version in Proceedings of ISIT 2018.","doi":"10.1109/TIT.2019.2907990","url_link":"https://ieeexplore.ieee.org/document/8676252","url_paper":"https://arxiv.org/abs/1712.07509","abstract":"We consider non-adaptive threshold group testing for identification of up to $d$ defective items in a set of $n$ items, where a test is positive if it contains at least $2 ≤ u ≤ d$ defective items, and negative otherwise. The defective items can be identified using $t = O ( ( \\frac{d}{u} )^u ( \\frac{d}{d - u} )^{d-u} (u łog{\\frac{d}{u}} + łog{\\frac{1}{ε}} ) · d^2 łog{n} )$ tests with probability at least $1 - ε$ for any $ε > 0$ or $t = O ( ( \\frac{d}{u} )^u ( \\frac{d}{d -u} )^{d - u} d^3 łog{n} · łog{\\frac{n}{d}} )$ tests with probability 1. The decoding time is $t × \\mathrm{poly}(d^2 łog{n})$. This result significantly improves the best known results for decoding non-adaptive threshold group testing: $O(nłog{n} + n łog{\\frac{1}{ε}})$ for probabilistic decoding, where $ε > 0$, and $O(n^u łog{n})$ for deterministic decoding. ","bibtex":"@ARTICLE{ref:BKCE19,\n author =\t {Thach V. Bui and Minoru Kuribayashi and Mahdi\n Cheraghchi and Isao Echizen},\n title =\t {Efficiently Decodable Non-Adaptive Threshold Group\n Testing},\n year =\t 2019,\n journal =\t {{IEEE Transactions on Information Theory}},\n volume =\t 65,\n number =\t 9,\n pages =\t {5519--5528},\n note =\t {Preliminary version in Proceedings of {ISIT 2018}.},\n doi =\t\t {10.1109/TIT.2019.2907990},\n url_Link =\t {https://ieeexplore.ieee.org/document/8676252},\n url_Paper =\t {https://arxiv.org/abs/1712.07509},\n abstract =\t {We consider non-adaptive threshold group testing for\n identification of up to $d$ defective items in a set\n of $n$ items, where a test is positive if it\n contains at least $2 \\leq u \\leq d$ defective items,\n and negative otherwise. The defective items can be\n identified using $t = O ( ( \\frac{d}{u} )^u (\n \\frac{d}{d - u} )^{d-u} (u \\log{\\frac{d}{u}} +\n \\log{\\frac{1}{\\epsilon}} ) \\cdot d^2 \\log{n} )$\n tests with probability at least $1 - \\epsilon$ for\n any $\\epsilon > 0$ or $t = O ( ( \\frac{d}{u} )^u (\n \\frac{d}{d -u} )^{d - u} d^3 \\log{n} \\cdot\n \\log{\\frac{n}{d}} )$ tests with probability 1. The\n decoding time is $t \\times \\mathrm{poly}(d^2\n \\log{n})$. This result significantly improves the\n best known results for decoding non-adaptive\n threshold group testing: $O(n\\log{n} + n\n \\log{\\frac{1}{\\epsilon}})$ for probabilistic\n decoding, where $\\epsilon > 0$, and $O(n^u \\log{n})$\n for deterministic decoding. }\n}\n\n","author_short":["Bui, T. V.","Kuribayashi, M.","Cheraghchi, M.","Echizen, I."],"key":"ref:BKCE19","id":"ref:BKCE19","bibbaseid":"bui-kuribayashi-cheraghchi-echizen-efficientlydecodablenonadaptivethresholdgrouptesting-2019","role":"author","urls":{" link":"https://ieeexplore.ieee.org/document/8676252"," paper":"https://arxiv.org/abs/1712.07509"},"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/writings/"}},"downloads":1,"html":""},"bibtype":"article","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-28T21:40:57.724Z","downloads":1,"keywords":[],"search_terms":["efficiently","decodable","non","adaptive","threshold","group","testing","bui","kuribayashi","cheraghchi","echizen"],"title":"Efficiently Decodable Non-Adaptive Threshold Group Testing","year":2019,"dataSources":["YZqdBBx6FeYmvQE6D"]}