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.