Randomness has become an indispensable tool in many areas of computer science: algorithm design, networking, error-correcting codes, cryptography, etc. While the use of randomness is unavoidable for certain applications (e.g., cryptographic constructions), other applications can be made completely deterministic. One of the main challenges of theoretical computer science is to understand the exact power of randomness in computation. In particular, it is a big open question whether every randomized polynomial-time algorithm has an equivalent deterministic polynomial-time algorithm (i.e., can be efficiently derandomized). Answering this question is important for algorithm design, as fast deterministic algorithms are usually preferable to randomized ones. On the other hand, there is a deep connection between trying to derandomize probabilistic algorithms and trying to prove lower bounds on the computational power of Boolean circuits. The latter problem has been actively researched for several decades with the goal of resolving the "P vs. NP" question. However, no strong circuit lower bounds are known for any explicit Boolean function.
In my research I try to explore various aspects of the basic question: to what extent is randomness useful in computation? A long-term goal of this research is to get a better understanding of randomized procedures (both algorithms and constructions of "random-like" combinatorial objects). Ideally, one would like to obtain deterministic constructions that match the parameters of known randomized constructions. Such constructions will provide more insight into the nature of "random-like" objects such as expander graphs, error-correcting codes, and randomness extractors, all of which have numerous practical applications. Eventually, this research may result in a unifying theory of "random-like" combinatorial objects, building upon already known connections among expanders, extractors, and error-correcting codes.