CS 535: Complexity Theory - Fall 2010

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.

Here are the past assignments: Homework 0, Homework 1, Homework 2, Homework 3, Homework 4, Homework 5.

Some selected (and brief) answers to problems from HW 6, answers to problems from HW 5, answers to problems from HW 3, answers to problems from HW 0.

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

Here are some new notes on extra topics including probabilistic complexity.

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 .

    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