Probabilistic Proof Systems

Oded Goldreich

September 1994


Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this exposition, we concentrate on three such proof systems -- interactive proofs, zero-knowledge proofs, and probabilistic checkable proofs -- stressing the essential role of randomness in each of them.

This exposition is an expanded version of a survey written for the proceedings of the International Congress of Mathematicians (ICM94) held in Zurich in 1994. It is hope that this exposition may be accessible to a broad audience of computer scientists and mathematians.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.