Oded Goldreich
The Meyer W. Weisgal Professor
My research interests lie in the theory of computing, specifically in
complexity theory, which is the general study of the nature and
limitations of efficient computations. Within this theory, I am most
interested in the interplay between randomness and computation
(e.g., pseudorandomness, probabilistic proof systems,
and property testing)
and in the foundations of cryptography.
For more details see
my
(extended) profile
and
my
list of recent publications.
In addition to plain research, I'm involved in various educational and expositional efforts. In particular, I wrote a two-volume book entitled Foundations of Cryptography (published in 2001 and 2004, resp.) as well as a number of surveys on Foundations of Cryptography, Pseudorandomness and Zero-Knowledge. Recently, I completed a book entitled Computational Complexity: A Conceptual Perspective.
Recent Publications
- [with M. Sudan] Locally testable codes and PCPs of almost-linear length. JACM 53: 4 (2006) 558-655.
- [with E. Ben-Sasson, P. Harsha, M. Sudan, and S. Vadhan] Robust PCPs of proximity, shorter PCPs and applications to coding. SICOMP (special issue on Randomness and Complexity) 36: 4 (2006) 889-974.
- [with D. Ron] Algorithmic aspects of property testing in the dense graphs model. ECCC Report TR08-039, April 2008.