MIT OpenCourseWare

Browse materialsMIT 18.405J · Spring 2016

Advanced Complexity Theory

Art: Anonymous painter,15th century, Westerner and Arab practicing geometry 15th century manuscript, 15th… · Public domain

Instructors: Prof. Dana Moshkovitz, Mohammad Bavarian
Term: Spring 2016
Level: Graduate
What's inside: 4 problem sets · 1 lecture note · 37 other files · 3 web pages
Materials open: MIT OCW

Start here

Start course: Lecture 1: PH Time-Space Tradeoffs (PDF) (Courtesy of anonymous…Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 18.405J Advanced Complexity Theory, Spring 2016, Prof. Dana Moshkovitz, Mohammad Bavarian — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. 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.

This course’s cited books, in our reading lists: Computational Complexity: A Modern Approach

How this course was organized

What's here, and what isn't

MIT's own materials here did not support a verified, course-wide order, so they are grouped by section instead.

Not included here

5 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. (5 items)

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Lecture Notes

16 files

Assignments

Projects

16 files

Other materials from this course

MIT OpenCourseWare, Prof. Dana Moshkovitz, Mohammad Bavarian, 18.405J Advanced Complexity Theory, Spring 2016.

License: CC BY-NC-SA 4.0 · Edition: Spring 2016 · 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.

Advanced Complexity Theory

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Assignments

Projects

Other materials from this course

Lecture 1: PH Time-Space Tradeoffs (PDF) (Courtesy of anonymous MIT student. Used with permission.)

Lecture 2: Relativization (PDF) (Courtesy of Di Liu. Used with permission.)

Lecture 3: Circuits and Karp-Lipton (PDF) (Courtesy of anonymous MIT student. Used with permission.)

Lecture 4: Unique-SAT, Parity-SAT, and Approximate Counting (PDF) (Courtesy of anonymous MIT student. Used with permission.)

Lecture 5: Toda’s Theorem (PDF) (Courtesy of Ilya Razenshteyn. Used with permission.)

Lecture 6: AC0 Lower Bounds and Switching Lemma (PDF) (Courtesy of Ilya Razenshteyn. Used with permission.)

Lecture 7: Razborov-Smolensky (PDF) (Courtesy of Brian Chen. Used with permission.)

Lecture 12: Randomized Communication (PDF) (Courtesy of Andrew He. Used with permission.)

Lecture 13: Karcher-Wigderson Games and KRW <Lecture notes not available>

Lecture 14: Intro to PCP (PDF)

Lecture 15: PCP Theorem Recap and FGLSS Reduction <Lecture notes not available>

Lecture 16: Linearity Testing (PDF) (Courtesy of anonymous MIT student. Used with permission.) Exponential Sized PCP (PDF) (Courtesy of Haoran Xu. Used with permission.)

Lecture 17: PCP with Polylogarithmic Queries and Sum Check (PDF) (Courtesy of Michael Forbes. Used with permission.)

Lecture 18: Unique Games Conjecture and Hardness for MAX-2LIN (PDF) (Courtesy of anonymous MIT student. Used with permission.)

Lecture 19: Parallel Repetition from Fortification <Lecture notes not available>

Lecture 20: P vs BPP 1 (PDF) (Courtesy of anonymous MIT student. Used with permission.)

Lecture 21: P vs BPP 2 (PDF) (Courtesy of anonymous MIT student. Used with permission.)

Lecture 22: Derandomization Implies Circuit Lower Bounds (PDF) (Courtesy of anonymous MIT student. Used with permission.)

Lecture 23: Natural Proofs <Lecture notes not available>