6.841[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.
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.
© Copyright 2015 Yasyf Mohamedali