Complexity Theory

Winter 2016/17

Course Outline

This is an introductory course in computational complexity theory. It is introductory in the sense that no prior knowledge in complexity theory is assumed. However, I do assume a basic understanding of algorithms and familiarity with the basics of theory of computation. For example, I assume you know the Big-O notation, algorithms on graphs (breadth first search, depth first search), regular languages and finite automata, and that you have seen Turing machines and know what is P and NP. The latter concepts will also be introduced and reviewed in the course.

Further, I expect you (1) have "mathematical maturity" (e.g., are comfortable with proofs and abstract reasoning); (2) are interested in the material; and (3) are willing to spend time outside of class in order to better understand the material presented in lectures.

Complexity theory is one of the most elegant branches of computer science. The goal of the course is to become familiar with some of the most beautiful results in our field.

Text book Arora and Barak, Computational Complexity: A Modern Approach.
Copies of the textbook will be available in the library. I will also provide lecture notes giving further details or covering topics not in that text.
If you are unsure whether this class is appropriate for you, I recommend you look at the Arora-Barak textbook to see whether you (a) find the topics interesting, and (b) find the level of difficulty appropriate.

The text book
Michael Sipser, Introduction to the theory of computation,
contains the material we will cover in the first few weeks as well as the required background for the class.

General Information



Syllabus (tentative)

Readings refer to Arora-Barak. In addition, we will post notes on individual lectures throughout the course of the semester. Feedback and corrections on the lecture notes are always appreciated!