CMSC 652 --- Complexity Theory

Fall 2011

Course Outline

This course will be an introductory graduate-level course in computational complexity theory. It is introductory in the sense that no prior knowledge in complexity theory is assumed, except that it is assumed students are familiar and comfortable with the notions of Turing machines, languages, classes, P/NP, and NP-completeness (but even these concepts will be reviewed quickly in the first lecture). On the other hand, the course will cover some fairly advanced (and abstract) material at a relatively quick pace; therefore, it is assumed that (1) students have "mathematical maturity" (e.g., are comfortable with proofs and abstract reasoning); (2) students are interested in the material; and (3) students are willing to spend time outside of class in order to better understand the material presented in class.

We will follow the text by Arora and Barak, supplemented with lecture notes giving further details or covering topics not in that text. The course will be similar to the previous offering.

If you are unsure whether this class is appropriate for you, I recommend you look at the Arora-Barak textbook (as well as the previous offering of the course) to see whether you (a) find the topics interesting, and (b) find the level of difficulty appropriate.

General Information and Announcements


Syllabus (tentative)

The entire set of lecture notes is available, in one file, here. Readings refer to Arora-Barak. Feedback and corrections on the lecture notes are always appreciated!