18.405[J] 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.405[J] will be offered this semester (Fall 2018). It is instructed by R. Williams.

This class counts for a total of 12 credits. This is a graduate-level class.

You can find more information at the http://www.google.com/search?&q=MIT+%2B+18.405&btnG=Google+Search&inurl=https site.

MIT 18.405[J] Advanced Complexity Theory Related Textbooks

© Copyright 2015