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 and
in the foundations of cryptography.
My recent and current research projects include the investigation of Locally Testable Codes (i.e., codes that admit very efficient codeword tests), the development of techniques for constructing good Probabilistically Checkable Proofs (with focus on the proof length), the initiation of a theory regarding the complexity of implementing random objects, the development of a session-key protocol using human passwords only, the initiation of the study of the security of cryptographic systems (say of Zero-Knowledge proofs) under resetting attacks, a demonstration of the impossibility of obfuscating program, and various studies concerning pseudorandomness as well as probabilistic proof systems.
In addition to the above, I'm involved in various educational and expositional efforts. In particular, I've written a two-volume book entitled "Foundations of Cryptography" (Volume 1 was published in 2001, and Volume 2 will be published in 2004) as well as a number of surveys on Foundations of Cryptography, Pseudorandomness and Zero-Knowledge. In addition, I have advised three PhD students: Boaz Barak, Yehuda Lindell and Alon Rosen.
Recent Publications
- [with M. Sudan] Locally Testable Codes and PCPs of Almost-Linear Length. In the Proceedings of the 43rd IEEE Symp. on Foundation of Computer Science, 2002, pp. 13-22.
- [with S. Goldwasser and A. Nussboim] On the Implementation of Huge Random Objects. In the Proceedings of the 44th IEEE Symp. on Foundation of Computer Science, 2003, pp. 68-79.
- [with B. Barak] Universal arguments and their applications. In the Proceedings of the 17th IEEE Conference on Computational Complexity, 2002, pp. 194-203.