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

11

Problem Set 1 (PDF)

Circuits can even look like this (PDF)

17

Problem Set 2 (PDF)

5 days after Lec #20

Problem Set 3 (PDF)

7 days after Lec #22

Problem Set 4 (PDF)