Computational Complexity Theory, Fall 2010

Course homepage for 2008 version

Latest news

January 13 2011
Scribe notes for lecture 24 available.
Page with exam information updated.

January 5 2011
Scribe notes for lecture 26 and 27 available.

December 14 2010
Page with exam information added.

December 13 2010
Scribe notes for lecture 16, 23, and 25 available.

December 9 2010
Homepage updated with lectures 26 and 27.

December 7 2010
Homepage updated with lecture 25.
Scribe notes for lecture 21 and 22 available.

December 5 2010
Mistake corrected in Homework 4, in the formulation of Problem 1.3.

December 2 2010
Homepage updated with lecture 24.

November 29 2010
Homework 4 posted. Due date: December 15.
Homepage updated with lecture 23.
Scribe notes for lecture 20 available.

November 27 2010
Scribe notes for lecture 18 and 19 available.

November 25 2010
Homepage updated with lecture 22.

November 23 2010
Homepage updated with lecture 21.

November 22 2010
Scribe notes for lecture 13 and 17 available.

November 16 2010
Homepage updated with lecture 20.
Announcement: No lecture on Friday, November 19.

November 11 2010
Homepage updated with lecture 19.

November 10 2010
Homework 3 posted. Due date: November 26.

November 9 2010 - NEWSFLASH
In lecture 16, last Wednesday I stated that it was an open problem, whether NEXP could be computed by (nonuniform) MOD2 o MOD3 o MOD2 circuits of polynomial size. This is no longer the case, as just proved by Ryan Williams! (See also news postings on several blogs here, here, and here)

Homepage updated with lecture 18.
Scribe notes for lecture 15 available.

November 2 2010
Homepage updated with lecture 16 and 17.

October 27 2010
Homepage updated with lecture 15.
Scribe notes for lecture 14 available.

October 5 2010
Homepage updated with lecture 14.
Scribe notes for lecture 11 and 12 available.

October 4 2010
Homepage updated with lecture 13.
Scribe notes for lecture 10 available.

September 29 2010
Homepage updated with lecture 12.
Scribe notes for lecture 9 available.

September 27 2010
Homepage updated with lecture 11.

September 23 2010
Scribe notes for lecture 7 and 8 available.
Homework 2 posted. Due date: October 8.

September 20 2010
Homepage updated with lecture 9 and 10.

September 15 2010
Scribe notes for lecture 5 and 6 available.

September 14 2010
Homepage updated with lecture 7 and 8.

September 8 2010
Scribe notes for lecture 3 and 4 available.

September 7 2010
Homepage updated with lecture 5 and 6.

September 3 2010
Homework 1 posted. Due date: September 17.

September 1 2010
Homepage updated with lecture 4.

August 31 2010
Homepage updated with lecture 3. Scribe notes for lecture 1 and 2 available.

August 21 2010
Homepage updated with lectures 1 and 2. Please note that the book by Hopcroft and Ullman is only accessible through the university network connection.