Graduate Computational Complexity

Fall 2010


Handouts

Date Topic
Dec 31 Algebrization: A New Barrier in Complexity Theory, by Scott Aaronson and Avi Wigderson [web-link]
Dec 31 Almost natural proofs, by Timothy Chow [web-link]
Dec 27 Problem-set 14 [pdf]
Dec 27 Problem-set 13 [pdf]
Dec 20 Problem-set 12 [pdf]
Dec 13 Problem-set 11 [pdf]
Dec 4 Problem-set 10 [pdf]
Nov 27 Problem-set 9 [pdf]
Nov 22 Problem-set 8 [pdf]
Nov 12 Problem-set 7 [pdf]
Nov 5 Survey on expansion by Hoory, Linial, and Wigderson [web-link]
Nov 5 Laszlo Lovasz's wonderful notes on random walks on graphs [web-link]
Nov 5 Problem-set 6 [pdf]
Oct 30 Problem-set 5 [pdf]
Oct 23 Problem-set 4 [pdf]
Oct 13 Problem-set 3 [pdf]
Oct 9 Problem-set 2 [pdf]
Sep 26 Problem-set 1 [pdf]
Sep 17 Course outline [pdf]