Advanced Complexity Theory
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.
Spring 2016
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.
Readings
Prerequisites & course information
Same subject as 6.5410J Prereq: 18.404 G (Spring) 3-0-9 units
Sources
- Course catalogue ↗2026–2027
- MIT OpenCourseWare ↗Spring 2016
- MIT OCW syllabus ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.