Derandomization and group testing
Derandomization and group testing
复制标题
DOI：
10.1109/allerton.2010.5707017
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
Mahdi Cheraghchi
中科院分区：
文献类型：
--
作者：
Mahdi Cheraghchi
去随机化理论是理论计算机科学中的一个基本领域，它的快速发展最近导致了许多超出其最初意图的令人惊讶的应用。我们将回顾一些最近的发展有关的组合群测试。在其最基本的设置中，组测试的目的是通过将项目分组并询问每组中是否有阳性个体来识别一组“阳性”个体。特别是，我们将讨论明确的最佳或接近最佳的组测试计划使用“随机传导”功能的建设。在这样的发展是建设的纠错组测试计划使用随机性提取器和冷凝器，以及阈值组测试计划从无损冷凝器。
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.