CS 642 Computational Complexity
Spring 2006

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. MW 4:00-5:15, Science Center 348.

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

Office Hours. M 2:30-4:00, Tu 3:30-5:00, W 1:00-3: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 in part on several homework assignments that will include simple exercises as well as challenging problems. These 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. We will also have a midterm and a final exam. In addition, each of you will do an oral presentation on an advanced topic.

Your course grade will be computed using the following formula:

50% Assignments + 15% Presentation + 15% Midterm test + 20% Final exam

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.