18.405J 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.
This class has 18.404 as a prerequisite.
18.405J will be offered this semester (Spring 2019). It is instructed by D. Moshkovitz.
This class counts for a total of 12 credits. This is a graduate-level class.
You can find more information on MIT OpenCourseWare at the Advanced Complexity Theory site.
© Copyright 2015 Yasyf Mohamedali