February 4th: Lecture 1. Interactive protocols.
DIP = coNP intersection NP. IP = PSPACE.
Literature: No handouts on this material, as I assume you all have
access to "Papadimitriou: Computational Complexity" where this is
covered (in particular, see pages 474-480). If somebody does not have
access to this book, let me know.
Scribe: Peter Frandsen. Scribe notes
February 11th: Lecture 2. Program checkers.
Multi-prover interactive protcols. MIP = NEXP proof, first part
Handout: Blum and Kannan, Designing Programs that check their work.
Virtual handout (replaces original handout): Blum and Kannan, Designing Programs that check their work.
Virtual handout: Babai et al: Nondeterministic exponential time has two
prover interactive protocols.
Scibe: M. Oliver Möller. Scribe notes
February 18th: Lecture 3. MIP = NEXP proof, second part, the
multilinarity test.
Handouts: Babai, Email and the unexpected power of interaction.
Feige et al: Approximating clique is almost NP-complete.
Virtual handout (replaces the Feige et al handout):
Feige et al: Interactive proofs and the hardness of approximating cliques.
Scribe: Rolf Fagerberg. Scribe notes
February 25th: No class (Peter away). While I'm gone, please look at these problems
March 4: No class (Peter away)
March 11: Lecture 4. MIP = NEXP proof, final part.
Self-testing/correcting pairs.
Scribe: Rasmus Pagh.
Scribe notes
March 18: Lecture 5. Scaling down the MIP = NEXP proof. Inapproximability of CLIQUE. Saving random- and query-bits in the BFL-protocol. Scribe: Rico Jakob. Scribe notes
March 25: Lecture 6. Saving random bits in the multilinearity test using small sample spaces. Scaling down the computational resources in the MIP = NEXP proof: Low degree extensions and low degree testing. Virtual Handout: Babai et al: Checking computations in polylogarithmic time. Scribe: Stefan Dantchev. Scribe notes
April 1: Easter Vacation
April 8: Lecture 7. Almost-linear sized oracles. Micali's computationally-sound proofs. Virtual handout: Micali: Computationally-sound proofs. Scribe: N.V. Vinodchandran Scribe notes
April 15: Lecture 8. Arora and Safra's PCP theorem. Recursive proof checking. Virtual handout: Arora and Safra: Probabilistic Checking of Proofs: A New Characterization of NP Scribe: Peter Frandsen. Scribe notes
April 22: Lecture 9. Arora and Safra's PCP theorem, continued. Improved low-degree test and making the pieces fit together.
April 29: Lecture 10. ALMSS's PCP theorem
Virtual handout: Arora et al: Proof Verification and the Hardness of Approximation Problems
May 6: No class (Peter away).
May 13: No class. Danish National Holiday (Kristi Himmelfartsdag).
May 20: Lecture 11. Proof of the improved low degree test. Virtual handout
May 27: Class canceled.
June 3: Lecture 12. Approximation lower bounds using the PCP theorem. Virtual handout: Arora and Lund: Hardness of Approximations
June 10: Lecture 13. The PCP theorem and coding theory. We discuss what came after