Probabilistic Proofs and NP-Completeness

(a course given by Jiri Sgall, spring 2002)

In this course we will cover the proof of  the PCP theorem and its implications for the hardness of approximation. Here are some pointers to texts used during the course, or providing an alternative coverage of the results. Some books covering parts of the proof of the PCP theorem or its relation to hardness of approximation are listed below.

Last changed June 4, 2002