MIT OpenCourseWare
Topics in Theoretical Computer Science: Probabilistically Checkable Proofs
Art: Johannes Kepler, Konjukce Saturnu a Jupiteru Originál, 1596 · Public domain
- Instructor
- Prof. Dor Minzer
- Term
- Fall 2022
- Level
- Graduate
- What's inside
- 5 problem sets · 1 lecture note · 13 other files · 2 web pages
- Materials open
- MIT OCW
About this course
Source: MIT OpenCourseWare 18.408 Topics in Theoretical Computer Science: Probabilistically Checkable Proofs, Fall 2022, Prof. Dor Minzer — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: none is claimed; materials are grouped by MIT's own sections. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.
Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.
Before you start
Prerequisites are not listed here. Check MIT's own syllabus for this course.
How this course was organized
What's here, and what isn't
- No lecture or session order could be confirmed for this course.
Not included here
4 items from the source could not be safely included:
- MIT's page format for this item wasn't recognized clearly enough to place it safely. (4 items)
Materials by section
Grouped by section, as MIT organized them. Not sequenced or ordered.
Lecture Notes
13 files
- 18.408 F2022 Lecture 1: Introduction Download
- 18.408 F2022 Lecture 9: A PCP with polylog Many Queries and Formalizations of PCPs Download
- 18.408 F2022 Lecture 12: Aggregation of Queries Download
- 18.408 F2022 Lecture 13: Hardness of Approximating the Maximum Clique Download
- 18.408 F2022 Lecture 16: The Set-cover Problem and A Reduction from Label-cover to Set-cover Download
- 18.408 F2022 Lecture 21: The Unique-Games Conjecture and the Goemans-Williamson Algorithm Download
- 18.408 F2022 Lectures 2–3: Error Correcting Codes Download
- 18.408 F2022 Lectures 4–6: Quadratic Solvability, Low-degree Extensions and the Sum-check Protocol Download
- 18.408 F2022 Lectures 7–8: Low Degree Testing Download
- 18.408 F2022 Lectures 10–11: Hadamard and Quadratic Hadamard Codes; The Composition Technique Download
- 18.408 F2022 Lectures 14–15: The Parallel Repetition Theorem Download
- 18.408 F2022 Lectures 17–20: The Long-code Paradigm and Some Optimal Inapproximability Results Download
- 18.408 F2022 Lectures 22–23: Unique-Games Hardness of Max-cut Download
Assignments
MIT OpenCourseWare, Prof. Dor Minzer, 18.408 Topics in Theoretical Computer Science: Probabilistically Checkable Proofs, Fall 2022.
License: CC BY-NC-SA 4.0 · Edition: Fall 2022 · Open the original course on OCW ↗
Organized by RedLectern, independent of MIT and not endorsed by MIT.
Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.