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 24.

There is no distinguished lecture this week but there is a "grad skills seminar at 11 on Tuesday. We will therefore meet Tuesday 10-11 and then again Wed 12-1. This week we will finish discussing basic properties of and examples of languages in the poly time randomized complexity classes. Periklis will start the discussion of IP and ZKIP.

There are now 3 questions on the final problem set and there may be one more. There was a typo in question 2 that has now been corrected. Namely, the question calls for a proof that there is a language L in EXPSPACE that is not in SIZE(M(n)-1) whereas it previously and erronously said that L was not in SIZE(M(n)).

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.