Valentine Kabanets

The proposed research is to study a number of complexity problems, especially those related to the role of randomness in computation. The big motivating questions are "BPP versus NEXP" and "RL versus L". The plan is also to work on explicit constructions of various "random-looking" combinatorial objects, both in terms of finding new constructions, and applying them to get interesting complexity theory results.