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, email@example.com.
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:
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.