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.