CS388T: Theory of Computation (Spring 2016)

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:

Topic Chapter
Diagonalization 3
Fine-Grained Complexity N/A
Polynomial Hierarchy 5
Boolean circuits 6
Randomized Computation 7
Interactive Proofs 8
PCPs and Inapproximability 11, 22.5
Communication Complexity 13
Circuit Lower Bounds 14
Complexity of Counting 17
Average Case Complexity 18
Pseudorandomness 20

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

Last modified: May 4, 2016