Open Course Space

Advanced Complexity Theory

Massachusetts Institute of TechnologyUnited States18.405J
Free, no sign-up neededSpring 2016English
Go to course on MIT OpenCourseWare

This graduate-level course focuses on current research topics in computational complexity theory. Topics include: 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.

Description from MIT OpenCourseWare.

Where to take this course