Periodical statements of Oded Goldreich

The 1994-2004 statements were prepared for the department's booklet, and the 2008 one for the web-site (which seems to have replaced the booklets). They were supposed to refer to research done in the last five years, and contain at most three publications. (See also research statements for MFO workshop on complexity.)


unsolicited statement for 2009-18

My research interests lie in the theory of computing, specifically in the interplay between randomness and computation. Two areas of interest are complexity theory, which is the general study of the nature and limitations of efficient computations, and property testing, which is the study of super-fast approximate decision procedures. Within complexity theory, I am most interested in pseudorandomnessand and probabilistic proof systems. For more details see my (extended) profile and my list of publications.

In addition to plain research, I'm involved in various educational and expositional efforts. In particular, I recently completed a textbook entitled Introduction to Property Testing.

Selected publications

  • [with D. Ron] On Proximity Oblivious Testing. SICOMP, Vol. 40, No. 2, pages 534-566, 2011.
  • [with B. Juba, and M. Sudan] A Theory of Goal-Oriented Communication. JACM Vol. 59, No. 2, Art. 8, 2012.
  • [with A. Wigderson] On Derandomizing Algorithms that Err Extremely Rarely. In 46th STOC, pages 109-118, 2014.
  • [with A. Tal] Matrix Rigidity of Random Toeplitz Matrices. In 48th STOC pages 91-104, 2016.
  • [with D. Ron] On Learning and Testing Dynamic Environments. JACM, Vol. 64, No. 3, pages 21:1-21:90, 2017.
  • [with G. Rothblum] Counting t-cliques: Worst-case to average-case reductions and direct interactive proof systems. ECCC TR18-046, 2018.

Statement for the Faculty Web-page (2008)

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 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, Vol. 53, No. 4, pages 558-655, 2006.
  • [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), Vol. 36, No. 4, pages 889-974, 2006.
  • [with D. Ron] Algorithmic aspects of property testing in the dense graphs model. ECCC Report TR08-039, April 2008.

Statement for the 2004 Booklet

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 developement 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 the Foundations of Cryptography, Pseudorandomness and Zero-Knowledge. In addition, I have advised three PhD students: Boaz Barak, Yehuda Lindell and Alon Rosen.

Recent Publications


Statement for the 1999 Booklet

My research interests lie in the theory of computing. Within this theory, I am most interested in the interplay between randomness and computation and in the foundations of cryptography. In general, I am interested in complexity theory, which is the study of the nature and limitations of efficient computations.

My recent and current research projects include the development of techniques for constructing good (if not optimal) probabilistically checkable proofs and for determining the level of approximation attainable by efficient algorithms for natural optimization problems, the initiation and investigation of Combinatorial Property Testing (the study of the complexity of determining whether a given object has a predetermined property or is ``far'' from any object having the property), the development of techniques for the design of zero-knowledge proofs (for example, a transformation of proofs which yield no knowledge to the prescribed verifier into ones which yield no knowledge to any verifier), and the re-examination of the Random Oracle Model/Methodology (which is extensively used recently in the design of practical cryptographic protocols).

In addition to the above, I'm involved in various educational and expositional efforts. In particular, I've published numerous surveys on topics related to the above, and wrote an introductory 200-pages text, entitled Modern Cryptography, Probabilistic Proofs and Pseudorandomness.

Recent Publications


Statement for the 1994 Booklet

In recent years, the investigation of the relations between randomness and computation and the application of randomness to computations, has become a central aspect of the theory of computation. In particular, the notions of pseudorandom generators, probabilistic proofs, weak random sources and constructions of small probability spaces have played an important role in the development of cryptography, complexity theory, and algorithmic design. Much of my research in the past, present and future is concerned with these notions. Following are a few words of clarification concerning two of the notions mentioned above.

Loosely speaking, a pseudorandom generator is an efficient (deterministic) program that stretches a randomly chosen seed into a much longer sequence, which nevertheless looks random to any efficient observer. Pseudorandom generators allow to shrink the amount of randomness used by any efficient randomized application program; namely, any application using a source of randomness can be modified so that it only uses much fewer, say 1000, coin tosses.

Various forms of probabilistic proof systems have been the focus of much attention in recent years. These non-traditional proof systems offer many advantages over the classical notion of a proof. For example, probabilistic proofs may be zero-knowledge in the sense that they leak nothing except the validity of the assertion being proven. Namely, whatever can be efficiently computed after getting a zero-knowledge proof, can be efficiently computed from the assertion itself. This paradoxical-looking notion has a tremendous effect on the design of cryptographic protocols, as has been demonstrated in some of my past works.

Recent Publications (not included originally)


Statement for the 1980's

Since I moved to Weizmann Institute in 1994, statements referring to previous periods were not made. In my e-records, I could only find a report referring to the academic year 1985-86 (and written for LCS's progress report to MIT). The first two paragraphs are reproduced below.
During the past year, Goldreich has been mainly interested in two topics: zero-knowledge proofs and software protection. In addition he improved the Goldwasser-Micali-Rivest signature sheme, and has been working with Chor on developing better schemes for extracting unbiased bits from weak sources of randomness.
Together with Prof. S. Micali (MIT) and A. Wigderson (UC-Berkeley), he has demonstrated the generality and wide applicability of zero-knowledge proofs, a fundamental notion intruduced by Goldwasser, Micali and Rackoff. Zero-knowledge proofs are probabilistic and interactive proofs that efficiently demonstrate membership in a language without conveying any additional knowledge. So far, zero-knowledge proofs has been known for some number theoretic languages in the intersection of NP and Co-NP. Under the assumption that encryption functions exist, it is shown that all languages in NP possess zero-knowledge proofs. This result is used to prove two fundamental theorems in the field of cryptographic protocols. These theorems consists of standard and efficient transformations that, given a protocol that is correct with respect to a very weak adversary, output a protocol correct in the most adversarial scenario. Using no assumptions, zero-knowledge proofs for both graph isomorphism and graph non-isomorphism, are presented.
A selected list of publications for the 1980's would have read as follows: I allowed myself a seventh paper (so to include one work from my graduate studies period) and ordered the papers by reverse chronological order (referring to the actual time they were first made public).


Back to Oded Goldreich's homepage.