Advanced Complexity Theory, Fall 2001
| Rating: | Not rated yet |
| Rate item | |
| Type: | Course Related Materials |
| Grade Level: | Post-secondary |
Author: Spielman, Daniel
Subject: Mathematics and Statistics, Science and Technology
Institution Name:
M.I.T.
Collection Name: MIT OpenCourseWare
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.
Details
Course Type: Full Course
Material Types: Homework and Assignments, Lecture Notes, Syllabi
Media Formats: Text/HTML, Downloadable docs
Language: English
Additional Information
Geographic
Regional Relevance: All
