Three Texts 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

Except for

- Probabilistic Proof Systems (survey), May 1995.

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. - A Taxonomy of Proof Systems, Dec. 1995 (revised Sept. 1996).

This survey was intended for readers with some background in computational complexity and is to appear in Complexity Theory Retrospective II. It provides a wider coverage than the first, but presents no constructions. - 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.