Remix and Share
Advanced Complexity Theory, Fall 2001
- Author: Spielman, Daniel
- Subject: Mathematics and Statistics, Science and Technology
- Institution Name: M.I.T.
- Collection: MIT OpenCourseWare
- Grade Level: Post-secondary
- Abstract: 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. The topics for this course cover various aspects of complexity theory, such as the basic time and space classes, the polynomial-time hierarchy and the randomized classes. This is a pure theory class, so no applications were involved.
- Course Type: Full Course
- Languages: English
- Material Types: Homework and Assignments, Lecture Notes, Syllabi
- Media Formats: Text/HTML, Downloadable docs
- Conditions of Use:
Creative Commons Attribution-Noncommercial-Share Alike 3.0
