Combinatorial Aspects of Randomness and Complexity

本项目研究两个相关领域：1。2.明确布尔函数复杂度的下界。复杂性理论背景下随机性的应用与理解。在第一个领域，目标是加强现有的证明有限计算模型下界的方法。寻找新的方法，可以用来分析无限制的模型，如一般布尔电路。PI将利用这些问题的无限类似来应用描述性集合论的概念。在第二个领域中，将考虑一些关于随机性的问题。重点介绍了扩展图作为一类通用随机对象的使用，以及伪随机生成的设计与应用。

This project studies two related areas: 1. Lower bounds on the complexity of explicit Boolean functions and 2. The application and understanding of randomness in the context of complexity theory. In the first area the goal is to strengthen current methods for proving lower bounds on restricted computational models. New approaches are sought that may be used to analyze unrestricted models such as general Boolean circuits. The PI will draw upon infinitary analogs of these problems to apply concepts from descriptive set theory. In the second area several problems concerning randomness will be considered. In particular, the use in of expanded graphs as a type of universal random object, and the design and application of pseudorandom generation.