CS 764—Computational Complexity

Spring 2014

Announcements

Instructor

Jonathan Buss, DC 3353, x34428, jfbuss%cs.uwaterloo.ca.

Office hours: Mondays and Wednesdays, 2:30–3:30. Please feel free to drop by with course questions or just to chat. You can often find me in at other times; email or phone to make sure.

Lectures

Mondays and Wednesdays, 9:30–11:00, DC 2568

Sources

The principal source will be

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

Aside from the material we will cover explicitly, it also makes a good reference on complexity theory. I recommend that you obtain your own copy.

The self-study module on finite fields is here.

The following references also have material of interest.

Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
(Less comprehensive than Arora and Barak, and lacking some recent material, but has very nice problem sections in each chapter.)

Uwe Schöning and Randall Pruim, Gems of Theoretical Computer Science, Springer, 1995.

Background required

You should be familiar with the basics of computational complexity: the Turing machine model, time and space bounds, complexity classes (e.g., P and NP), and complete problems. For those who have taken UW courses, either CS 365 or both CS 360 and CS 341 will suffice.

Syllabus

Syllabus continually under construction.

Assigned problems

The problem sets will have both basic and advanced problems. Doing only basic problems can earn you up to an A- on the assignment component of your mark. Advanced problems can (a) make up for missing basic problems and (b) raise your assignment component up to an A+.

Hand in your solutions to the basic problems by the specified due date (at the start of class).

If you submit solutions for the advanced problems by the due date, I will give you feedback on them; in any case, you may submit solutions to advanced problems until the last day of lecture.

First problem set now available: PDF. Due date May 28 June 2.

Do your own work on all problems. If you inadvertantly run across a solution somewhere, consult the instructor as soon as possible.

Projects/Essays

Schedule:

Outlines due: Wednesday, July 8, in class.
Presentations: TBA (Jul. 23–30).
Papers due: Monday, August 11, by noon, to DC 3353.

We will schedule project presentations during the last two weeks of classes. Depending on class size, some presentations may be outside the usual lecture time.

For fuller information, see the PDF file, or consult the instructor.

Jonathan Buss
June 2014