The course starts by laying the basic framework and
results of computational complexity theory and then studies in
detail some of the achievements of the past two decades, such
Towards the end we will put draw upon the expertise we have
built up over the term to understand recent results such as Ryan
Williams' 2011 result separating NEXP from ACC0.
Prerequisites: COS 340/341 or equivalent math background
(basically, ability to do math proofs). Some exposure to theory
of computation at an undergrad level is recommended, though not
Interested undergrads should contact the instructor. Undergrads and grads will be graded separately.
Grading: 60% of the grade will be based upon
assignments, which will be handed out every two weeks. 40% will
be based upon a long take-home final (open book).
Every student taking the course will have the responsibility to grade the homework once during the term, under my supervision.
There might also be a small course project at the end of the
ALL COURSE HANDOUTS ARE IN ADOBE ACROBAT FORMAT. DOWNLOAD ACROBAT READER HERE.
These are the instructor's notes (to himself) about what topics
were covered in each lecture.The goal is solely to help the
students (and the instructor!) recall the contents of
Honor Code for this class
Collaborating with your classmates on assignments is encouraged (and may be essential to get the most out of the course). You must, however, list your collaborators for each problem. The assignment questions have been carefully selected for their pedagogical value and may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.