Omer Reingold
Incumbent of the Walter and Elise Haas Career Development Chair
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 Michael R. Capalbo, Salil P. Vadhan, Avi Wigderson] Randomness conductors and constant-degree lossless expanders. STOC 2002, 659-668.
- [with Salil P. Vadhan, Avi Wigderson] Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. FOCS 2000, 3-13
- [with Moni Naor] Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions. J. of Computer and System Sciences 58 (2) (1999) 336-375.