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