Derandomization and Group Testing. Cheraghchi, M. In Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing, pages 991–997, 2010. Link Paper doi abstract bibtex 5 downloads The rapid development of derandomization theory, which is a fundamental area in theoretical computer science, has recently led to many surprising applications outside its initial intention. We will review some recent such developments related to combinatorial group testing. In its most basic setting, the aim of group testing is to identify a set of "positive" individuals in a population of items by taking groups of items and asking whether there is a positive in each group. In particular, we will discuss explicit constructions of optimal or nearly-optimal group testing schemes using "randomness-conducting" functions. Among such developments are constructions of error-correcting group testing schemes using randomness extractors and condensers, as well as threshold group testing schemes from lossless condensers.
@INPROCEEDINGS{ref:conf:Che10,
author = {Mahdi Cheraghchi},
title = {Derandomization and Group Testing},
year = 2010,
booktitle = {Proceedings of the 48th {Annual Allerton Conference
on Communication, Control, and Computing}},
pages = {991--997},
doi = {10.1109/ALLERTON.2010.5707017},
url_Link = {https://ieeexplore.ieee.org/document/5707017},
url_Paper = {https://arxiv.org/abs/1010.0433},
abstract = { The rapid development of derandomization theory,
which is a fundamental area in theoretical computer
science, has recently led to many surprising
applications outside its initial intention. We will
review some recent such developments related to
combinatorial group testing. In its most basic
setting, the aim of group testing is to identify a
set of "positive" individuals in a population of
items by taking groups of items and asking whether
there is a positive in each group. In particular,
we will discuss explicit constructions of optimal or
nearly-optimal group testing schemes using
"randomness-conducting" functions. Among such
developments are constructions of error-correcting
group testing schemes using randomness extractors
and condensers, as well as threshold group testing
schemes from lossless condensers. }
}
Downloads: 5
{"_id":"sudEC4v2kJyhTvzfR","bibbaseid":"cheraghchi-derandomizationandgrouptesting-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":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]}],"title":"Derandomization and Group Testing","year":"2010","booktitle":"Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing","pages":"991–997","doi":"10.1109/ALLERTON.2010.5707017","url_link":"https://ieeexplore.ieee.org/document/5707017","url_paper":"https://arxiv.org/abs/1010.0433","abstract":"The rapid development of derandomization theory, which is a fundamental area in theoretical computer science, has recently led to many surprising applications outside its initial intention. We will review some recent such developments related to combinatorial group testing. In its most basic setting, the aim of group testing is to identify a set of \"positive\" individuals in a population of items by taking groups of items and asking whether there is a positive in each group. In particular, we will discuss explicit constructions of optimal or nearly-optimal group testing schemes using \"randomness-conducting\" functions. Among such developments are constructions of error-correcting group testing schemes using randomness extractors and condensers, as well as threshold group testing schemes from lossless condensers. ","bibtex":"@INPROCEEDINGS{ref:conf:Che10,\n author =\t {Mahdi Cheraghchi},\n title =\t {Derandomization and Group Testing},\n year =\t 2010,\n booktitle =\t {Proceedings of the 48th {Annual Allerton Conference\n on Communication, Control, and Computing}},\n pages =\t {991--997},\n doi =\t\t {10.1109/ALLERTON.2010.5707017},\n url_Link =\t {https://ieeexplore.ieee.org/document/5707017},\n url_Paper =\t {https://arxiv.org/abs/1010.0433},\n abstract =\t { The rapid development of derandomization theory,\n which is a fundamental area in theoretical computer\n science, has recently led to many surprising\n applications outside its initial intention. We will\n review some recent such developments related to\n combinatorial group testing. In its most basic\n setting, the aim of group testing is to identify a\n set of \"positive\" individuals in a population of\n items by taking groups of items and asking whether\n there is a positive in each group. In particular,\n we will discuss explicit constructions of optimal or\n nearly-optimal group testing schemes using\n \"randomness-conducting\" functions. Among such\n developments are constructions of error-correcting\n group testing schemes using randomness extractors\n and condensers, as well as threshold group testing\n schemes from lossless condensers. }\n}\n\n","author_short":["Cheraghchi, M."],"key":"ref:conf:Che10","id":"ref:conf:Che10","bibbaseid":"cheraghchi-derandomizationandgrouptesting-2010","role":"author","urls":{" link":"https://ieeexplore.ieee.org/document/5707017"," paper":"https://arxiv.org/abs/1010.0433"},"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/writings/"}},"downloads":5,"html":""},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T00:28:13.096Z","downloads":5,"keywords":[],"search_terms":["derandomization","group","testing","cheraghchi"],"title":"Derandomization and Group Testing","year":2010,"dataSources":["YZqdBBx6FeYmvQE6D"]}