Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
This MIT OpenCourseWare graduate course covers the theory of Probabilistically Checkable Proofs (PCPs) and its consequences for computational complexity. The first half builds the algebraic proof of the basic PCP Theorem and connects it to hardness of approximation for combinatorial optimization problems. The second half covers advanced topics including hardness amplification, the long-code framework, the Unique-Games Conjecture, and the 2-to-2 Games Theorem. Materials include lecture notes and problem sets from MIT's course, free to access through OCW with no certificate offered. The course is aimed at graduate students with a strong background in theoretical computer science and complexity theory, and it draws on recent research advances alongside foundational results from the 1990s PCP literature.