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.

随机性提取是一个算法过程，它将具有低质量随机性的对象转换为具有高质量随机性的对象。这些对象（通常称为源）可以是有限的概率分布，有限的二进制字符串和无限的二进制序列，并且分别通过最小内侧面，kolmogorov的复杂性和建设性的Hausdorff尺寸来测量随机性质量。在所有三个设置中，都存在大量关于随机提取的工作。我们的项目将通过调查在开发主要当前技术和工具的一些基本假设的情况下调查随机提取的情况来扩展该领域。 在某些应用中，涉及概率分布是独立的假设是有问题的。因此，试图纠正有缺陷来源的算法应能够以有限的独立性处理来源。 该项目将研究从具有有限独立性的两个或多个来源的随机提取问题，与当前仅考虑完全独立来源的文献相比。 扩展一些部分结果，目的是建立可以从此类来源获得的随机性质量的上限，并设计在上限附近执行的有效提取器。该项目的另一项研究行致力于曝光弹性提取器，这些过程是有效的过程，这些过程设法提取了一些看起来随机的位，即使是对具有自适应访问输入源的对手的随机过程。 目的是设计具有适用于密码应用应用的参数的提取器。随机提取是一个非常活跃的领域，并且是构思的孵化器，即使在该地区以外也有重大影响。拟议的研究开辟了新的研究方向，这些方向是自然而具有挑战性的。它在随机提取的研究中增加了新的维度，并具有扩大提取器应用范围的潜力。随机提取在计算复杂性，随机算法，建设性组合学，密码学，错误校正代码和其他领域中具有应用。该项目试图使许多这些应用程序更实用，更健壮。该项目将在计算复杂性，Kolmogorov复杂性和算法信息理论之间建立新的联系。该项目将允许本科生和研究生参加具有强烈理论风味和现实应用的希望的研究活动。