Probabilistic Proof Systems
Papers and Expositions by Oded Goldreich
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.
Four expositions (available on-line)
- 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.
-
- O. Goldreich,
On doubly-efficient interactive proof systems,
2018.
Chapters in Books
Additional related material available on-line
Papers available on-line
Papers that focus on zero-knowledge proofs
(or on Knowledge Complexity)
are not included in the following list.
(These papers are available from the webpages
on zero-knowledge
and Knowledge Complexity.)
- 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