18.405[J] 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.405[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 at the http://www.google.com/search?&q=MIT+%2B+18.405&btnG=Google+Search&inurl=https site.
© Copyright 2015 Yasyf Mohamedali