RJLRef: $PH/09s304/readings_resources.htm (last update: 20090126)

See textbook resources for errata corrections to Sipser text (2ed)

Links to prior semesters at UML and MIT: prior_course_offerings.htm.

Online resources: There are plenty of these:

In addition to the MIT Open Courseware Notes (from classes using Sipser), there is an overlapping course by Scott Aaronson at MIT, 06.080: Great Ideas in Theoretical Computer Science, whose Spring 2008 course is archived at the Open Courseware site at MIT:

MIT OCW 6-080 Great Ideas in Theoretical Computer Science

From its home page I extracted this comment:

Comparison of Aaronson and Sipser courses

The web site Complexity Theory Companion from U Rochester has multiple slide sets (600 in all!) covering the first seven chapters of Hemaspaandra and Ogihara's text by that name (Springer-Verlag, 2002). Caveat: Complexty Theory Companion is an advanced graduate text and the slides are by its students. Here is the Table of Contents:

Chapter 1, The Self-Reducibility Technique

Chapter 2, The One-Way Function Technique

Chapter 3, The Tournament Divide and Conquer Technique

Chapter 4, The Isolation Technique

Chapter 5, The Witness Reduction Technique

Chapter 6, The Polynomial Interpolation Technique

Chapter 7, The Nonsolvable Group Technique

Chapter 8; The Random Restriction Technique

Chapter 9; The Polynomial Technique

Appendices:

A. Rogues Gallery of Complexity Classes

B. Rogues Gallery of Reductions