Computational Complexity (Spring 2007)

This course describes attempts to answer a fundamental question of CS namely: What can computers solve efficiently?

Some Bibliography:

This course does not have a textbook. However, every week following the lectures I will post link(s) to relevant material that is available online. Most of this material is going to be from two books that are currently being written:

Some of the topics (at least in the beginning of the course) are also covered in the following books.

Exercises:

Lectures: