Several alternative formulations of the concept of an efficient proof system
are nowadays coexisting in Theoretical Computer Science.
These systems include the classical formulation of **NP**,
as well as the newer notions of *interactive proof systems*
(giving rise to the class **IP**),
*computationally-sound proof systems*,
and *probabilistically checkable proofs*
(**PCP**, which are closely related to
*multi-prover interactive proofs* (**MIP**).
Although these notions are sometimes introduced using the same
generic phrases, they are actually very different in motivation,
applications and expressive power.

Except for **NP**, all proof systems reviewed are probabilistic
and furthermore have a non-zero error probability. However, the error
probability is explicitly bounded and can be reduced by successive
applications of the proof system. In all cases, non-zero error probability
is essential to the interesting properties and consequences which these
probabilistic proof systems have.

- O. Goldreich,
Probabilistic Proof Systems - A Primer,
June 2008.

This is the latest and most recommended exposition. It provides a comprehensive treatment of the basic notions and results, and contains proof outlines and/or sketches for the main results.

(This text is an abbreviated and self-contained version of Chapter 9 in Computational Complexity: A Conceptual Perspective.) - O. Goldreich,
Probabilistic
Proof Systems (survey), May 1995
(revised,
Dec. 1996).

This survey was intended for a general audience and has appeared in the proceedings of*ICM94*, the International Congress of Mathematicians 1994. It focuses on the very basics and presents some well-known constructions. - O. Goldreich,
A
Taxonomy of Proof Systems, Dec. 1995 (revised Sept. 1996).

This survey was intended for readers with some background in computational complexity and appeared in the*Complexity Theory Retrospective II*. It provides a wider coverage than the first, but presents no constructions. - O. Goldreich,
Probabilistic
Proof Systems (Lecture Notes), Sept. 1996.

These are lecture**notes**in the strict sense of the word. They were prepared for a series of lectures given in the Theory Student Seminar of the CS Department of UC-Berkeley.

- Chapter 9 in Computational Complexity: A Conceptual Perspective (2008) provides a revised and extended version of the above.
- Chapter 4 in Foundations of Cryptography (Vol. 1, 2001) provides an extensive treatment of zero-knowledge.
- Chapter 2 in Modern Cryptography, Probabilistic Proofs and Pseudorandomness (1998) surveys various types of probabilistic proof systems.

- S. Vadhan, Lecture notes on Probabilistic Proof Systems - Part I (interactive and zero-knowledge proofs), 2000.
- M. Sudan, Lecture notes on Probabilistic Proof Systems - Part II (probabilistically checkable proofs), 2000.
- O. Goldreich, webpage on zero-knowledge (including a tutorial).

- B. Barak and O. Goldreich, Universal Arguments and their Applications, 2001 (rev. 2007)
- M. Bellare and O. Goldreich, On Defining Proofs of Knowledge, 1992. See also notes on Proofs of Computational Ability (1992).
- M. Bellare, O. Goldreich and S. Goldwasser, Randomness in Interactive Proofs, August 1991. (See also an Addendum, May 1997.)
- M. Bellare, O. Goldreich and M. Sudan, Free Bits, PCPs and Non-Approximability, 1995.
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan, Robust PCPs of Proximity, Shorter PCPs and Applications to Coding, March 2004.
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan, Short PCPs verifiable in polylogarithmic time, 2005
- R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad, D. Ranjan and P. Rohatgi, The Random Oracle Hypothesis is False, July 1992.
- M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos, On Completeness and Soundness in Interactive Proof Systems, 1989.
- O. Goldreich and S. Goldwasser, On the Limits of Non-Approximability of Lattice Problems, Sept. 1997.
- O. Goldreich and J. Hastad, On the Complexity of Interactive Proof with Bounded Communication, Feb. 1996. (rev. April 1997)
- O. Goldreich, and S. Safra, A Combinatorial Consistency Lemma with application to the PCP Theorem, 1996.
- O. Goldreich and M. Sudan, Locally Testable Codes and PCPs of Almost-Linear Length, August 2002.
- O. Goldreich, S. Vadhan, and A. Wigderson, On Interactive Proofs with a Laconic Prover, 2001.

Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers