##
Course on Probabilistically Checkable Proofs and Hardness of
Approximation, March 2003 - June 2003

by Uri Feige

Take home exam, 30 June 2003.
Hand in by August 1, 2003.

Lecture notes:
Lecture 1, 5 and 12 March 2003:
Introduction to the PCP theorem.

Lecture 2, 19 March 2003:
Interactive Verification of co-NP statements.

Lecture 3, 26 March and 2 April 2003:
NP is in PCP(log n, polylog n).

Lecture 4, 9 April 2003:
The degree-h test.

Lecture 5, 14 May 2003:
Outer verifiers and inner verifiers.

Lecture 6, 21 and 28 May 2003:
Techniques for parallelization.

Lecture 7, 28 May and 4 June 2003:
A constant number of query bits.

Lecture 8, 11 June 2003:
Tight inapproximability results.

Handouts (homework) for course.

Handout 1, 12 March 2003:
Introduction to the PCP theorem.

Handout 2, 19 March 2003:
The LFKN protocol.

Handout 3, 26 March 2003:
NP is in PCP(log n, polylog n).

Handout 4, 9 April 2003:
The degree-h test.

Handout 5, 21 May 2003:
Parallelization of probes.

Handout 6, 28 May 2003:
NP is in PCP(log n, polyloglog n).

Handout 7, 4 June 2003:
A constant number of query bits.