6.5410J/18.405J Advanced Complexity Theory
Repeats every week every Tuesday and every Thursday until Tue May 13 2025 except Tue Feb 18 2025, Tue Mar 25 2025, Thu Mar 27 2025.
Tue, 02/04/2025 - 11:00am to 12:30pmLocation:
4-163
Instructor:
Dor Minzer
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.