Omer Reingold
The focus of my research lies mainly
in the fields of computational complexity and the foundations of cryptography.
More specifically, a substantial part of my research is concentrated on the
notions of pseudorandomness and derandomization: Randomization is one of the
most pervasive paradigms in computer science, with widespread use in areas including
algorithm design, cryptography, coding theory, network design, and interactive
proofs. However, it is still not known to what extent the randomness is really
necessary in these settings, and understanding this is important for both practical
and theoretical reasons. The main approach to addressing this issue is via the
paradigm of pseudorandomness, which is the theory of generating objects that
"look random" despite being constructed using little or no randomness. In my
research I was interested in pseudorandomness in cryptography, and in the construction
of "pseudorandom combinatorial objects" such as expander graphs and randomness
extractors. Finally, I am particularly interested in the tradeoff between memory
and randomness. Namely, I am interested in whether randomness can significantly
reduce the memory needed for computational tasks.
Recent Publications
- [with R. Gradwohl] Partial exposure and correlated types in large games. Manuscript (2008).
- [with I. Haitner] Statistically-hiding commitment from any one-way function. STOC 2007 (2007) 1-10.
- Undirected ST-connectivity in log-space. STOC 2005 (2005) 376-385.