CS 642 Computational Complexity
Spring 2008

Official Course Description. The complexity of a computational problem is the amount of computing resources it requires. Computational complexity theory studies the complexity of important computational problems as well as relationships between different types of resources. This course will cover both classical and research-related topics in computational complexity. Students will gain experience reading research papers. A presentation may be required.

Prerequisites. CS345 or CS541.

Location and Times. MWF 9:00-9:50, Science Center 303.

Instructor. Alexis Maciel. Science Center 379, 268-2385, alexis@clarkson.edu.

Office Hours. M 10:00-11:30, Tu 10:00-11:00, W 2:30-4:00, Th 10:00-11:00.

Required Text. None. We will use a set of lectures notes by Dave Barrington and the instructor. These will be available on the course web page. We will most likely cover some sections of the following textbook:

Copies of the relevant sections will be distributed, if necessary. We will also read various research papers. Copies will be distributed.

Course Objectives.

  1. To learn basic concepts and results of computational complexity.

  2. To become familiar with some of the current research topics in computational complexity.

  3. To gain experience reading research papers in theoretical computer science.
Demonstrable outcomes. By the end of the semester,
  1. You will be familiar with and understand basic results and research-related topics in computational complexity.

  2. You will be able to solve problems related to this material.

  3. You will be able to read and understand research papers in computational complexity.

Tentative list of topics. Complexity measures and complexity classes for sequential machines and Boolean circuits, reductions and completeness, hierarchy theorems, relativization, small-depth circuit complexity, proof complexity.

Grading. Your evaluation will be based on homework assignments (A), a presentation (P), a midterm test (T), a test correction (C) and a final exam (F). Your course grade will be computed using the following formula:

45% A + 10% P + 20% T + 5% C + 20% F

The homework assignments will include simple exercises as well as challenging problems. They will be related to the material presented in class or to the research papers assigned for reading. Homework assignments may also include brief reports on those papers. The oral presentation will be on an advanced topic, most likely from a research article. The final exam will not be cumulative. At the final exam, you will have the option of writing a make-up for the midterm test. Tentative date for the midterm test: Wednesday, March 5. This will be an evening exam. All students are required to write the final exam (no exemptions).

Policy for missed work. There will be no make-up assignments. Late assignments may be accepted if a good excuse is provided and if arrangements are made at a reasonable time, in advance, if possible. Make-up tests can be arranged under the same conditions. Other special arrangements can be made for students forced to miss more than a few days of class.