18.405J / 6.841J Advanced Complexity Theory

As taught in: Fall 2001

A nested Venn diagram.

Two levels of the complexity hierarchy. (Image by Prof. Daniel Spielman.)

Level:

Graduate

Instructors:

Prof. Daniel Spielman

Course Features

Course Description

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.