Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
18.408 · Mathematics · Graduate · Fall 2022
Prof. Dor Minzer
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 Gam…
The syllabus, on MIT OpenCourseWare
The full course — syllabus, assigned readings, problem sets, exams, and lecture notes — lives on OCW. These open the real thing:
Syllabus ↗
Course overview, grading, schedule
Readings ↗
The assigned reading list, session by session
Assignments ↗
Problem sets and projects
Full course on OCW ↗
Everything, including lecture materials
Attribution
Prof. Dor Minzer. 18.408 Topics in Theoretical Computer Science: Probabilistically Checkable Proofs. Fall 2022. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: CC BY-NC-SA 4.0.
Course materials are © their authors and licensed CC BY-NC-SA 4.0. CurrMana links to the source and does not re-host them.