Advanced Complexity Theory
MIT OpenCourseWare's graduate seminar surveys current research in computational complexity theory. Lecture notes and readings cover nondeterministic, alternating, probabilistic, and parallel computation models, Boolean circuits, complexity classes and complete sets, and the polynomial-time hierarchy. Later sessions examine interactive proof systems and probabilistically checkable proofs, relativization, definitions of randomness, and pseudo-randomness and derandomization. The course is built around research papers and problem sets rather than a textbook, reflecting its focus on open questions in the field. Materials are published freely through MIT OpenCourseWare, including syllabus, assignments, and lecture notes, with no enrollment or certificate fee. It suits students who already have a background in basic computational complexity and want exposure to the techniques driving current theoretical computer science research.