| 1 | Course Overview
Review
P-Completeness and the Circuit Value Problem (CVP) | (PDF) (Courtesy of Shaun Cutts and Dr. Zulfikar Ramzan. Used with permission.) | Scribe: Shaun Cutts
Lecturer: Daniel A. Spielman |
| 2 | Alternation
Relations to Deterministic Classes | (PDF) (Courtesy of Yu Chen. Used with permission.) | Scribe: Yu Chen
Lecturer: Daniel A. Spielman |
| 3 | Polynomial Hierarchy | (PDF) (Courtesy of Shanghua Teng, and Hoe Teck Wee. Used with permission.) | Scribe: Hoeteck Wee
Lecturer: Shanghua Teng |
| 4 | Polynomial Hierarchy (cont.)
The Polynomial Time Hierarchy Collapses
Non-Uniform Complexity | (PDF) (Courtesy of Matthew Lepinski. Used with permission.) | Scribe: Matthew Lepinski
Lecturer: Daniel A. Spielman |
| 5 | NP and P/poly
Circuit Complexity | (PDF) (Courtesy of Adam Winkel. Used with permission.) | Scribe: Adam Winkel
Lecturer: Daniel A. Spielman |
| 6 | Relativization, The Baker-Gill-Solovay Theorem
Randomized Computation | (PDF) | Lecturer: Daniel A. Spielman |
| 7 | BPP Error Amplification
Verifying Polynomial Identities | (PDF) (Courtesy of Abhinav Kumar. Used with permission.)
Handout (PDF) | Scribe: Abhinav Kumar
Lecturer: Daniel A. Spielman |
| 8 | The Valiant-Vazirani Theorem
Universal Hash Functions | (PDF) (Courtesy of Aram Harrow. Used with permission.) | Scribe: Aram Harrow
Lecturer: Daniel A. Spielman |
| 9 | Counting Classes
Toda's Theorem | (PDF) (Courtesy of David Liben-Nowell. Used with permission.) | Scribe: David Liben-Nowell
Lecturer: Daniel A. Spielman |
| 10 | Quantum Computation | (PDF) (Courtesy of Christopher Avrich. Used with permission.) | Scribe: Christopher D. Avrich
Lecturer: Daniel A. Spielman |
| 11 | Quantum Complexity | (PDF) (Courtesy of Daniel Preda. Used with permission.) | Scribe: Daniel Preda
Lecturer: Daniel A. Spielman |
| 12 | Fourier Transform
Discrete Log Problem
Calculable Quantum Fourier Transforms
Sufficiency of these Transforms | (PDF) (Courtesy of Jonathan Herzog. Used with permission.) | Scribe: Jonathan Herzog
Lecturer: Daniel A. Spielman |
| 13 | Oracle Quantum Turing Machines | (PDF) (Courtesy of Abhinav Kumar. Used with permission.) | Scribe: Abhinav Kumar
Lecturer: Daniel A. Spielman |
| 14 | Reusing Random Bits for BPP Algorithms: Definitions, Analysis | (PDF) | Lecturer: Daniel A. Spielman |
| 15 | Interactive Proofs
Zero-Knowledge Proofs
Arthur-Merlin Games | (PDF) (Courtesy of Gregory Dennis. Used with permission.) | Scribe: Gregory Dennis Lecturer: Shanghua Teng |
| 16 | Interactive proofs of graph non-isomorphism | (PDF) (Courtesy of Paul Chang. Used with permission.) | Scribe: Paul M. Chang
Lecturer: Daniel A. Spielman |
| 17 | Recap of Arthur-Merlin Games
Graph Isomorphism
Probabilistically Checkable Proofs
3SAT Approximation is NP-hard | (PDF) (Courtesy of Ronnie Misra. Used with permission.) | Scribe: Ronnie Misra
Lecturer: Daniel A. Spielman |
| 18 | #P ⊆ IP
PSPACE ⊆ IP | (PDF) (Courtesy of Sergi Elizalde (Doctor of Mathematics). Used with permission.) | Scribe: Sergi Elizalde
Lecturer: Daniel A. Spielman |
| 19 | Recall Proof Strategy of PSPACE ⊆ IP
Implicit Circuit Sat and the Proof Outline
Multilinear Polynomials
The Multilinearity Test | (PDF) (Courtesy of Kenneth McCracken. Used with permission.) | Scribe: Ken McCracken
Lecturer: Daniel A. Spielman |
| 20 | The Multilinearity Test (cont.) | (PDF) (Courtesy of Jan Vondrák. Used with permission.) | Scribe: Jan Vondrák
Lecturer: Daniel A. Spielman |
| 21 | Approximating Max-Clique
Reducing Satisfiable Clauses in 3CNF | (PDF) (Courtesy of Hiroyoshi Iwashima. Used with permission.) | Scribe: Hiro Iwashima
Lecturer: Daniel A. Spielman |
| 22 | Derandomizing Logspace Computations | (PDF) | Lecturer: Daniel A. Spielman |