CSC2401 Home Page (Fall 2008)

This page will provide WWW access to various documents concerning CSC2401. Announcements will also be made on this page.

Announcements for week of November 17.

There is a distinguished lecture this week so we will only have one hour of lecture on Tuesday (10-11). There will be a lecture on Wednesdday 12-1 in the standard room BA2179. This week we will finish discussing Boolean circuits. Then we will start randomized complexity.

There are now 3 problems on the final problem set and there may be more.

Please send any comments or questions to the instructor:

bor..at..cs.toronto.edu

This course is a standard graduate level introduction to complexity. The course will be related to previous versions of this course but this year the course will be more of a foundational course in the sense that we will be focusing somewhat more on the classical results in the field with less emphasis on more current research activity. The text is ``Introduction to the Theory of Computation: Second Edition'' by Michael Sipser. A supplemental text is ``Theory of Computation'' by Dexter Kozen.

There are a number of other text books in this area. One excellent advanced text that has just been published is Oded Goldrich's Computational Complexity . Another soon to be published excellent advanced text is Sanjeev Arora and Boaz Barak's Complexity Theory:A Modern Approach. A draft of this text is available on thei web site. Although the course will be somewhat different, in many regards the the course will be similar to the versions taught in 2001, 2003, 2005 and 2007.