| Syllabus: | Syllabus. | ||||||||||||||||||||||||||
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: GDC 4.508 Phone: 471-9729 Office Hours: T 2-3, Th 3:30-4:30. | ||||||||||||||||||||||||||
| TA: | Fu Li
Email: fuli.theory.research@gmail.com 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 | ||||||||||||||||||||||||||
| Topics: |
|
||||||||||||||||||||||||||
| 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). | ||||||||||||||||||||||||||
| Useful References: |
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 |