Office: GDC 4.508
Office Hours: T 2-3, Th 3:30-4:30.
Office (for office hours): GDC 1.302, Desk 1
Office (for all other purposes): GDC 4.504D
Office Hours: M 4-5, F 3:30-4:30.
|Required Text:||Arora and Barak, Computational Complexity: A Modern Approach|
|Final Exam:||The final exam will be cumulative and held in the usual classroom on Wednesday, May 11 from 2-5pm. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary).|
Virginia Williams talk
Hardness for Easy Problems, an Introduction
Dominik Scheder's chapter Sparsification and ETH
Simple BPP algorithm for primality
Ryan O'Donnell's text Analysis of Boolean Functions