6.841J 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.

6.841J 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 at the index.html site.

MIT 6.841J Advanced Complexity Theory Related Textbooks
MIT 6.841J Advanced Complexity Theory On The Web
tex lecture notes scribe pdf

© Copyright 2015