| 1 | Course Overview
Review
P-Completeness and the Circuit Value Problem (CVP) | |
| 2 | Alternation
Relations to Deterministic Classes | |
| 3 | Polynomial Hierarchy | |
| 4 | Polynomial Hierarchy (cont.)
The Polynomial Time Hierarchy Collapses
Non-Uniform Complexity | |
| 5 | NP and P/poly
Circuit Complexity | |
| 6 | Relativization, The Baker-Gill-Solovay Theorem
Randomized Computation | |
| 7 | BPP Error Amplification
Verifying Polynomial Identities | |
| 8 | The Valiant-Vazirani Theorem
Universal Hash Functions | |
| 9 | Counting Classes
Toda's Theorem | |
| 10 | Quantum Computation | |
| 11 | Quantum Complexity | Problem set 1 due |
| 12 | Fourier Transform
Discrete Log Problem
Calculable Quantum Fourier Transforms
Sufficiency of these Transforms | |
| 13 | Oracle Quantum Turing Machines | |
| 14 | Reusing Random Bits for BPP Algorithms: Definitions, Analysis | |
| 15 | Interactive Proofs
Zero-Knowledge Proofs
Arthur-Merlin Games | |
| 16 | Interactive proofs of graph non-isomorphism | |
| 17 | Recap of Arthur-Merlin Games
Graph Isomorphism
Probabilistically Checkable Proofs
3SAT Approximation is NP-hard | Problem set 2 due |
| 18 | #P ⊆ IP
PSPACE ⊆ IP | |
| 19 | Recall Proof Strategy of PSPACE ⊆ IP
Implicit Circuit Sat and the Proof Outline
Multilinear Polynomials
The Multilinearity Test | |
| 20 | The Multilinearity Test (cont.) | Problem set 3 due before next lecture |
| 21 | Approximating Max-Clique
Reducing Satisfiable Clauses in 3CNF | |
| 22 | Derandomizing Logspace Computations | Problem set 4 due (a week after this lecture) |