CS 535: Complexity Theory - Fall 2008

Welcome to the home page for the Computer Science Department's Complexity course CLA CS 535. This is the starting point for online course information and documentation.

Here is the most recent CS 535 Course News.

Here is the current HOMEWORK, due on September 9.

Past homework assignments:

-- Homework 1 . And answers to 4 of the problems from HW 1.

-- Homework 0 . And answers to two of the problems from HW 0.

There is a list of corrections to the text which will be updated from time to time.

CS 535 is the department's introductory graduate course on the theory of computation. The following list of pointers provides access to information concerning the course, the students and the department.

• Course Information
  • Syllabus
  • Homework
  • A couple of other complexity course pages are here and here and here. The first of these, course notes by Jin-Yi Cai of Wisconsin, may be particularly useful for this class.
  • For grading purposes, here is a list of people in the class.
  • There are many more. And there are even complexity Poems courtesy of Harry Mairson.
• Boston University and Computer Science Department Information
  • CS Department Home Page
  • CS Department Computing Resources
  • Other Departmental Resources
  • CS Department Colloquia.
  • Boston University WWW Server