CMSC 652 Complexity Theory, Fall 2017Course DescriptionComputational complexity theory studies the power of computation in terms of consumed computational resources such as time, memory, communication, number of rounds of communication, and randomness. It deals with fundamental questions such as:
This course is an introductory graduatelevel course in computational complexity theory. 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 NPcompleteness (which will be reviewed quickly in the first week). 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. A tentative list of covered topics includes basic time and space complexity classes (e.g., P, NP, PSPACE, polynomial hierarchy), randomized computation, interactive proof systems, as well as more advanced topics such as the PCP theorem, circuit lower bounds, and pseudorandomness. If you are unsure whether this class is appropriate for you, you are recommended to look at the Arora and Barak textbook (as well as the previous offerings of the course) to see whether you (a) find the topics interesting, and (b) find the level of difficulty appropriate. Generics
AssignmentsHomework assignments must be submitted electronically to ELMS. (Anyone having trouble with electronic submissions should contact the instructor as soon as possible.) I highly recommend the use of for the typesetting. Here is a good reference about the use of . Here is a latex template for writing solutions.
Textbooks & LecturesWe will follow the text by Arora and Barak, supplemented with lecture notes giving further details or covering topics not in that text. It will be similar to the previous offering (by Prof Gasarch (Spring 2014), by Prof Katz (Fall 2011), and by Prof Srinivasan (Fall 2009). Recommended references include:
Useful resources include: Complexity Zoo. Social Media
