CS 764

CS 764—Computational Complexity

Spring 2014

Announcements

Information on projects now available.
Problem Set 2 now available. Basic problems due Monday, June 23.
Adjustments to lecture schedule:

Cancelled Replacement date Room

May 21 June 6 (Fri) DC 3313

June 11 June 20 (Fri) DC 3313

mid-July (tba) tba
Problem set 1 has been revised:
- The problem on parity has been clarified: the depth of a circuit does not include the negations. See the revised version for a bit more detail.
- Problem 3, part a, asked for an incorrect time bound. The correct bound is t(f(n)).
  Also, the definition of expand is slightly modified. This modification does not affect the problem in any significant way; it only makes the write-up slightly simpler.
The due date has changed to Monday, June 2 (early submission permitted).
The instructor will be absent on Wednesday, May 21. Class will still happen, however; students should discuss the exercises on finite fields.
(If the room is locked, ask the grad receptionist (DC 2599) to let you in.)
Problem set 1 now available. See below for general information on problem sets.

Cancelled	Replacement date	Room
May 21	June 6 (Fri)	DC 3313
June 11	June 20 (Fri)	DC 3313
mid-July (tba)	tba

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