New Directions in the Study of Randomness Extractors

项目摘要：抽取器是从较低质量的随机性中产生高质量随机性的有效过程。它们在许多地区都是基本的积木原语，因此受到了广泛的研究。该项目在几个新的重要方向上扩展了对萃取器的研究。广义地说，目标是构建具有显著更好的效率和健壮性的抽取器。具体地说，一个目标是设计按位局部可计算的抽取器，它是伪随机函数的信息论模拟。这样的抽取器在时间上以弱随机串的长度的多对数分别产生它们的每个输出位。另一个目标是研究抗暴露能力强的萃取器。这些萃取器比标准萃取器更强大，因为它们通过了统计测试，根据随机性的来源进行自适应调整。抗曝光抽取器在密码学和概率次线性时间算法的去随机化中有应用，包括在属性测试和机器学习中的算法。该项目调查了建造具有优越参数的抗曝光萃取器的可能性，研究了可实现参数的下限，并探索了这类萃取器的应用领域，这似乎是广阔的。智力上的功绩。这项研究解决了新的和具有挑战性的自然问题。它承诺建立具有在理论和实际应用中具有实际影响的属性的萃取器。已经取得了一些初步成果，需要开发新的技术。抗暴露萃取器的概念为萃取器的研究增加了一个新的维度，并为一些新的应用打开了可能性。抽取器在随机化算法、构造性组合学、密码学、纠错码等领域有着广泛的应用。这项研究将使其中许多应用程序更实用、更健壮。该项目的某些部分可能会对目前与采掘者没有联系的领域产生影响，例如财产测试。该项目将允许本科生和研究生参与具有强烈理论气息和现实应用前景的研究活动。这将有助于在Towson大学新的博士学位项目中建立一条理论路线。结果将在美国和国外的研讨会和会议上公布，并将广泛传播。

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.