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:

- Michael Sipser,

**Course Objectives.**

- To learn basic concepts and results of computational complexity.
- To become familiar with some of the current research topics in computational complexity.
- To gain experience reading research papers in theoretical computer science.

- You will be familiar with and understand basic results and research-related topics in computational complexity.
- You will be able to solve problems related to this material.
- 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:

**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.