MIT Subject Listing & Schedule
IAP/Spring 2026 Search Results

Searched for:

1 subject found.

6.5410[J] Advanced Complexity Theory

()
(Same subject as 18.405[J])
Prereq: 18.404
Units: 3-0-9
Lecture: TR2.30-4 (3-270) +final

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.
R. Williams
No textbook information available