New Directions in the Study of 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.