CMSC 652 --- Complexity Theory

Fall 2005


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; it is assumed that (1) students 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.

The class will roughly be organized as follows: The first 2/3 of the course will cover "standard" material on complexity theory (e.g., the material in lectures 1-12 of Goldreich's lecture notes); the remainder of the course will focus on more advanced topics (such as derandomization of space- and time-bounded algorithms, the PCP theorem, circuit lower bounds, learning theory, cryptography, and/or other topics). Note: You do not need to print out all of Goldreich's lecture notes, especially since we will only be following them loosely (in particular, there will be many topics we skip, a few that we add, and we will definitely cover things in a different order). However, you may find it helpful to consult his notes for further clarification of things covered in class.

If you are unsure whether this class is appropriate for you, I recommend you check out Goldreich's notes (referenced above) to make sure that you (a) find the topics interesting, and (b) find the level of difficulty appropriate. You can also feel free to email me with any questions.

The requirements are: There may also be occasional ungraded homeworks that will be discussed in class if there is interest.

General Information and Announcements

Homeworks

Tentative Lecture Schedule

The lecture notes are intended to supplement lectures, and do not necessarily cover everything discussed in class. They may also contain some things that we did not have time to cover in class. This material is based upon work supported by the National Science Foundation under Grant Nos. 0310499, 0310751, 0426683, and 0447075. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.