Slides:

• Lectures 1-4 (were taught on a whiteboard): Search and decision problems. Polynomial-time many-one, Levin's, Turing reductions. NP-completeness, search-to-decision, NP-intermediate problems. Introduction to PH.
• Lecture 5: The Polynomial Hierarchy.
• Lecture 6: The Karp-Lipton Theorem. Fixed-polynomial lower bounds. Introduction to space complexity.
• Lecture 7: PSPACE, L, NL, P-completeness.
• Lecture 8: Savitch's Theorem. The Immerman-Szelepcenyi Theorem. Parallel computation. Padding.
• Lecture 9: Randomized computation: ZPP, RP, BPP.
• Lecture 10: BPP vs P/poly and PH. The Valiant-Vazirani Lemma. Relativization. Introduction to interactive protocols.
• Lecture 11: Interactive protocols.
• Lecture 12: Two more examples of interactive protocols. The PCP Theorem.