AF: Small: Studies in Randomness Extraction

AF：小：随机性提取的研究

• 批准号: 1016158
• 负责人: Marius Zimand
• 金额: $ 22.39万
• 依托单位: Towson University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016158&HistoricalAwards=false
• 关键词: AF; Small; Studies; Randomness; Extraction

Randomness extraction is an algorithmical process that transforms objects with low-quality randomness into objects with high-quality randomness. The objects (usually called sources) can be finite probability distributions, finite binary strings, and infinite binary sequences, and the randomness quality is measured, respectively, by min-entropy, Kolmogorov complexity, and constructive Hausdorff dimension. There exists a vast amount of work on randomness extractions in all three settings. Our project will extend the field by investigating randomness extraction in situations that go beyond some of the basic assumptions for which the main current techniques and tools have been developed. In some applications, the assumption that the involved probability distributions are independent is problematic. Therefore, an algorithm that attempts to remedy defective sources should be able to handle even sources with bounded independence. The project will study the issue of randomness extraction from two or more sources with bounded independence, in contrast with the current literature that has only considered the case of fully independent sources. Extending some partial results, the objective is to establish upper bounds on the quality of randomness that can be obtained from such sources and to design efficient extractors that perform in the vicinity of the upper bounds. Another research line of the project is dedicated to exposure-resilient extractors, which are efficient procedures that manage to extract bits that look random even to an adversary that has adaptive access to the input sources. The objective is to design such extractors with parameters suitable for applications in cryptography.Randomness extraction is a very active field and has been an incubator of ideas with a significant impact even outside the area. The proposed research opens new directions of study that are natural and challenging. It adds new dimensions in the study of randomness extraction and has the potential of enlarging the range of applications of extractors. Randomness extraction has applications in computational complexity, randomized algorithms, constructive combinatorics, cryptography, error-correcting codes, and other areas. The project attempts to make many of these applications more practical and more robust. The project will establish new connections between computational complexity, Kolmogorov complexity, and algorithmical information theory. The project will allow undergraduate and graduate students to participate in research activities that have a strong theoretical flavor and the promise of real-world applications.

随机性提取是将低质量随机性对象转换为高质量随机性对象的算法过程。对象（通常称为源）可以是有限概率分布、有限二进制串和无限二进制序列，随机性质量分别通过最小熵、柯尔莫哥洛夫复杂度和构造豪斯多夫维来测量。在这三种设置中都存在大量关于随机性提取的工作。我们的项目将通过研究超出当前主要技术和工具已开发的一些基本假设的情况下的随机性提取来扩展该领域。 在某些应用中，所涉及的概率分布是独立的假设是有问题的。因此，尝试修复有缺陷的源的算法应该能够处理具有有限独立性的源。 该项目将研究从两个或多个具有有限独立性的来源中随机提取的问题，这与当前仅考虑完全独立来源的情况的文献形成鲜明对比。 扩展一些部分结果，目标是建立可以从这些来源获得的随机性质量的上限，并设计在上限附近执行的高效提取器。该项目的另一个研究方向致力于暴露弹性提取器，这是一种有效的程序，能够提取看似随机的位，甚至对于能够自适应访问输入源的对手来说也是如此。 目的是设计具有适合密码学应用的参数的提取器。随机性提取是一个非常活跃的领域，并且一直是思想的孵化器，即使在该领域之外也产生了重大影响。拟议的研究开辟了自然且具有挑战性的新研究方向。它为随机性提取的研究增加了新的维度，并有可能扩大提取器的应用范围。随机性提取在计算复杂性、随机算法、构造组合学、密码学、纠错码和其他领域都有应用。该项目试图使许多这些应用程序更加实用和强大。该项目将在计算复杂性、柯尔莫哥洛夫复杂性和算法信息论之间建立新的联系。该项目将允许本科生和研究生参与具有浓厚理论色彩和现实应用前景的研究活动。