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)

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.)
Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers