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.

Languages:

English

Material Type:

Full Course, Homework and Assignments, Lecture Notes, Syllabi

Media Format:

Text/HTML, Downloadable docs

Conditions of Use:

Creative Commons Attribution-Noncommercial-Share Alike 3.0