Topics in Theoretical Computer Science
Study of areas of current interest in theoretical computer science. Topics vary from term to term.
Fall 2022 · Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
In this course, we will present the theory of Probabilistically Checkable Proofs (PCPs), and prove some fundamental consequences of it as well as more recent advances. More specifically, the first half of the course will be devoted to the (algebraic) proof of the basic PCP Theorem and basic relation to approximation problems. We will then move on to more advanced topics, such as hardness amplification, the long-code framework, the Unique-Games Conjecture and its implications, and the 2-to-2 Games Theorem.
Prerequisites & course information
Prereq: Permission of instructor Acad Year 2027-2028: Not offered Acad Year 2028-2029: G (Spring) 3-0-9 units Can be repeated for credit.
Sources
- Course catalogue ↗2026–2027
- MIT OpenCourseWare ↗Fall 2022
- MIT OCW syllabus ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.