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.
