This course will introduce students to the area of computational complexity theory. We will focus on topics including complexity classes, lower bounds, the role of randomness in computations. This will be a theoretical course: we will take a pen-and-paper approach and avoid computer implementations and other empirical studies. That is, we establish results in the form of mathematical theorems.
The course is in the Theory Track.
Prerequisites
CSCE 235 and 310 are prerequisites for the course. In particular a good knowledge of basic combinatorial techniques and probability theory is necessary. Familiarity with algorithms (CSCE 423/823 or equivalent) and automata theory (CSCE 428/828 or equivalent) are recommended for understanding the course material faster. But students with certain level of mathematical maturity will be able to make very good use of the course without the knowledge of algorithms or automata.
Textbook
We will not be using any specific textbook as there are plenty of materials on the topics that we plan to cover available on the web. In particular, the web draft of the forthcoming book (title: Complexity Theory: A Modern Approach) due to Professors Sanjeev Arora and Boaz Barak of Princeton University, available on Prof. Sanjeev Arora's personal web-page, gives a very comprehensive treatment of complexity theory.
Venue: 112, Avery Hall
Time : TuTh 9:30pm - 10:50pm