New Directions in the Study of Randomness Extractors

随机性提取器研究的新方向

• 批准号: 0634830
• 负责人: Marius Zimand
• 金额: $ 12.53万
• 依托单位: Towson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-15 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0634830&HistoricalAwards=false
• 关键词: New; Directions; Study; Randomness; Extractors

Project Abstract: Extractors are efficient procedures that produce high-quality randomness from lower-quality randomness. They are a basic building-block primitive in many areas and consequently they have been studied intensively. The project extends the investigation of extractors in several new important directions. Broadly speaking, the goal is to build extractors with significantly better efficiency and robustness.Specifically, one objective is to design bitwise locally computable extractors which are the information-theoretical analogue of pseudo-random functions. Such extractors produce each of their output bits separately in time polylogarithmic in the length of the weakly-random string. Another objective is the study of exposure-resilient extractors. These extractors are stronger than standard extractors in that they pass statistical tests that adjust themselves adaptively depending on the source of randomness. Exposure-resilient extractors have applications in cryptography and in the derandomization of probabilistic sublinear-time algorithms, including algorithms in property testing and machine learning. The project investigates the possibility of constructing exposure-resilient extractors with superior parameters, studies lower bounds on the achievable parameters, and explores the field of applications of such extractors, which appears to be vast. Intellectual Merit. The research tackles natural problems that are new and challenging. It has the promise to build extractors with attributes that have a real impact in theoretical and practical applications. Some preliminary results have already been obtained and they required the development of novel techniques. The concept of exposure-resilient extractors adds a new dimension in the study of extractors and opens the possibility of some new applications.Broader Impact. Extractors have applications in randomized algorithms, constructive combinatorics, cryptography, error-correcting codes, and other areas. This research will make many of these applications more practical and more robust. Some parts of the project are likely to have implications in areas that currently are not linked to extractors such as property testing. 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. It will help in establishing a theoretical line in the new doctorate program at Towson University. The results will be communicated at seminars and conferences in the US and abroad and will be made widely available.

项目摘要：提取器是从低质量随机性产生高质量随机性的有效程序。它们是许多领域的基本建筑块原始性，因此对它们进行了深入研究。该项目将提取器的调查扩展到几个新的重要方向。从广义上讲，目的是建立具有更高效率和鲁棒性的提取器。特别是，一个目的是设计局部可计算的提取器，这是伪随机函数的信息理论类似物。此类提取器在弱随机字符串的长度上分别产生其每个输出位。 另一个目的是研究暴露弹性提取器。这些提取器要比标准提取器强，因为它们通过统计测试，根据随机性的来源，可以自适应地调整自己。暴露弹性提取器在密码学和概率sublrinear-time算法的范围内具有应用，包括属性测试和机器学习中的算法。该项目研究了具有出色参数的构建暴露弹性提取器的可能性，对可实现的参数进行了较低的界限，并探讨了这种提取器的应用领域，这些萃取器似乎很广泛。智力优点。该研究解决了新的和具有挑战性的自然问题。 它有望建立具有对理论和实际应用具有真正影响的属性的提取器。已经获得了一些初步结果，他们需要开发新技术。曝光 - 提取器的概念在研究器的研究中增加了一个新的维度，并打开了一些新应用的可能性。提取器在随机算法，建设性组合学，密码学，错误校正代码和其他领域中具有应用。这项研究将使许多这些应用程序更加实用，更强大。该项目的某些部分可能在目前与诸如属性测试之类的提取物链接的领域有影响。该项目将允许本科生和研究生参加具有强烈理论风味和现实应用的希望的研究活动。它将有助于在陶森大学的新博士学位课程中建立理论线。结果将在美国和国外的研讨会和会议上进行传播，并将广泛使用。