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

6.841[J] will not be offered this semester. It will be instructed by R. Williams.

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 or on the 6.841[J] Stellar site.

MIT 6.841[J] Advanced Complexity Theory Related Textbooks
MIT 6.841[J] Advanced Complexity Theory On The Web
Advanced Complexity Theory

© Copyright 2015