Computation is omnipresent in society, and randomness plays an important role, both as a liability and as a commodity. In particular, the ability to flip fair coins seems surprisingly useful in a plethora of computational settings, and a central line of research in the theory of computing tries to determine its actual power. In that context researchers develop deterministic simulations of randomized processes that are as efficient as possible. The canonical approach entails the construction of pseudo-random generators, which are efficient deterministic procedures that stretch a short random coin flip sequence to a much longer sequence that still looks random to the process under investigation. The driving question of the project is whether this canonical approach is omnipotent or whether there exist better ways to obtain deterministic simulations.
The project focuses on the relationships between derandomization, pseudo-random generators, and lower bounds. The existence of efficient pseudo-random generators is known to be equivalent to certain types of circuit lower bounds (which remain open). There are also a number of results showing that derandomization implies circuit lower bounds of some sort, but the lower bounds are typically not strong enough so as to imply back the same derandomization. A major thrust of the project is to establish equivalences between circuit lower bounds and derandomization, implying that canonical derandomization through pseudo-random generators is omnipotent.
The PI and his coworkers have developed a framework for deriving such results, and intend to apply it to large classes of randomized processes, including efficient decision procedures and efficient verification processes known as Arthur-Merlin games. The main focus lies on the standard notion of derandomization, in which the simulation needs to be correct everywhere, but the PI will as well consider weaker notions in which the deterministic simulation is allowed to err on some inputs.
Apart from furthering our knowledge about the power of randomness in computation, the project aims to provide graduate training on that topic and in the broader area of computational complexity.
