6.5410J / 18.405J Advanced Complexity Theory
Repeats every week every Tuesday and every Thursday until Tue May 12 2026 except Tue Feb 17 2026, Tue Mar 24 2026, Thu Mar 26 2026.
Tue, 02/03/2026 - 2:30pm to 4:00pmLocation:
3-270
Instructor:
Ryan Williams
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.