# 18.405 Advanced Complexity Theory

**Catalog description:**

Current research topics in computational complexity theory. Nondeterministic, alternating, probabilistic, and parallel computation models. Boolean circuits. Complexity classes and complete sets. The polynomial-time hierarchy. Interactive proof systems. Relativization. Definitions of randomness. Pseudo-randomness and derandomizations. Interactive proof systems and probabilistically checkable proofs.

Also see the math departmentâ€™s subject overview for theoretical computer science.

Resources:

- Spring 2024 in-class scribe lecture notes
- Spring 2022 class website
- Spring 2016 OCW (lecture notes, homework, example projects)