18.405J Advanced Complexity Theory

Class Info

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 not be offered this semester. It will be available in the Spring semester, and will be 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.

MIT 18.405J Advanced Complexity Theory Related Textbooks
MIT 18.405J Advanced Complexity Theory On The Web
Advanced Complexity Theory
hierarchy theory

© Copyright 2015