Some of the previous versions of this course:
2005,
2004.
Announcements:
- July 12: The entire book has been posted below.
- June 26: Papadimitriou's errata is now
working.
- June 26: The last lecture will be on Friday, June 29, and the
topic will be Toda's theorem. The last assignment, assignment 4, is
also due on Friday.
- June 26: Chapters 6 and 7, as well as the Appendix, are
available belwo. Chapter 6 has been proof read, while Chapter 7 and
the Appendix are in a preliminary stage.
- June 14: Chapter 5, proof read by Jan Jezabek, has been posted
below.
- June 10: As was announced in class on Friday, there will be no
lecture on Tuesday June 12th. We shall continue as usual on Friday
June 15, with a lower bound for resolution proving the PHP.
- June 1: A second version of Chapter 2 with comments/corrections
by Grzegorz Gutowski has been posted.
- May 31: Feel free to hand in assignment 2 on Friday June 8th,
during the lecture.
- May 31: On Tuesday June 5th, Greg Herman will be presenting two
results (during the usual lecture time, 10-12): Razborov's lower
bound for circuits computing CLIQUE, and Razborov-Smolensky's lower
bound for circuits with modular gates.
- May 29: Chapter 4 has been just posted.
- May 28: I just posted a second version (v2) of chapter 2, after
the corrections of Bartosz Walczak. I also posted a second version of
chapter 1, with minor corrections, and with a solution to Q2 from
assignment 1.
- May 24: A very useful resource in complexity is the
Complexity
Zoo.
- May 21: A premliminary version of chapter 3 has been posted, as
well as assignment 2.
- May 10: Discussion
Forum.
- May 7:
The P versus NP Problem (new link May 22,
2007).
Lecture Notes:
Proof readers:
- Lech Duraj: chapter 3
- Greg Herman: chapters 1,2,3,4,5,6,7,8
- Bartosz Walczak: chapter 2
- Grzegorz Gutowski: chapter 4
- Jan Jezabek: chapter 5
Click here for the entire
book.
Assignments: