Complexity Theory Courses


6.045J Automata, Computability, and Complexity 
 (Same subject as 18.400J)

Professor: S. Aaronson

Prereq: 6.042

Units: 4-0-8

Lecture: TR2.30-4 (32-141) Recitation: F11 (34-301) or F2 (34-302) +final

Provides an introduction to some of the central ideas of theoretical computer science, including circuits and decision trees, finite automata, Turing machines and computability, efficient algorithms and reducibility, the P versus NP problem, NP-completeness, the power of randomness, cryptography and one-way functions, computational learning theory, and quantum computing. Examines the classes of problems that can and cannot be solved in various computational models.


6.440 Essential Coding Theory 

Professors: M. Sudan, D. Moshkovitz

Prereq: 6.006, 6.045

Units: 3-0-9

Lecture: MW11-12.30 (26-204)

Introduces the theory of error-correcting codes. Focuses on the essential results in the area, taught from first principles. Special focus on results of asymptotic or algorithmic significance. Principal topics include construction and existence results for error-correcting codes; limitations on the combinatorial performance of error-correcting codes; decoding algorithms; and applications to other areas of mathematics and computer science.


6.840J Theory of Computation 
(Same subject as 18.404J)

Professor: M. Sipser

Prereq: 18.310 or 18.062J

Units: 4-0-8

A more extensive and theoretical treatment of the material in 6.045J/18.400J, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.


6.841J Advanced Complexity Theory 
(Same subject as 18.405J)

Professor: D. Moshkovitz

Prereq: 18.404

Units: 3-0-9

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.


6.842 Randomness and Computation 

Professor: R. Rubinfeld

Prereq: 6.046, 6.840

Units: 3-0-9

The power and sources of randomness in computation. Connections and applications to computational complexity, computational learning theory, cryptography and combinatorics. Topics include: probabilistic proofs, uniform generation and approximate counting, Fourier analysis of Boolean functions, computational learning theory, expander graphs, pseudorandom generators, derandomization.


6.845 Quantum Complexity Theory 

Professor: S. Aaronson

Prereq: 6.045, 6.840, 18.435

Units: 3-0-9

Introduction to quantum computational complexity theory, the study of the fundamental capabilities and limitations of quantum computers. Topics include complexity classes, lower bounds, communication complexity, proofs and advice, and interactive proof systems in the quantum world; classical simulation of quantum circuits. The objective is to bring students to the research frontier.


Please click here to view courses related to CIS at MIT.