Courses:

Advanced Complexity Theory >> Content Detail



Lecture Notes



Lecture Notes

The names of scribes for the lectures are noted in the table below.

LEC #TOPICSLECTURE NOTESSCRIBES / LECTURERS
1Course 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
2Alternation

Relations to Deterministic Classes
(PDF) (Courtesy of Yu Chen. Used with permission.)Scribe: Yu Chen

Lecturer: Daniel A. Spielman
3Polynomial Hierarchy(PDF) (Courtesy of Shanghua Teng, and Hoe Teck Wee. Used with permission.)Scribe: Hoeteck Wee

Lecturer: Shanghua Teng
4Polynomial 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
5NP and P/poly

Circuit Complexity
(PDF) (Courtesy of Adam Winkel. Used with permission.)Scribe: Adam Winkel

Lecturer: Daniel A. Spielman
6Relativization, The Baker-Gill-Solovay Theorem

Randomized Computation
(PDF)Lecturer: Daniel A. Spielman
7BPP Error Amplification

Verifying Polynomial Identities
(PDF) (Courtesy of Abhinav Kumar. Used with permission.)

Handout (PDF)
Scribe: Abhinav Kumar

Lecturer: Daniel A. Spielman
8The Valiant-Vazirani Theorem

Universal Hash Functions
(PDF) (Courtesy of Aram Harrow. Used with permission.)Scribe: Aram Harrow

Lecturer: Daniel A. Spielman
9Counting Classes

Toda's Theorem
(PDF) (Courtesy of David Liben-Nowell. Used with permission.)Scribe: David Liben-Nowell

Lecturer: Daniel A. Spielman
10Quantum Computation(PDF) (Courtesy of Christopher Avrich. Used with permission.)Scribe: Christopher D. Avrich

Lecturer: Daniel A. Spielman
11Quantum Complexity(PDF) (Courtesy of Daniel Preda. Used with permission.)Scribe: Daniel Preda

Lecturer: Daniel A. Spielman
12Fourier 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
13Oracle Quantum Turing Machines(PDF) (Courtesy of Abhinav Kumar. Used with permission.)Scribe: Abhinav Kumar

Lecturer: Daniel A. Spielman
14Reusing Random Bits for BPP Algorithms: Definitions, Analysis(PDF)Lecturer: Daniel A. Spielman
15Interactive Proofs

Zero-Knowledge Proofs

Arthur-Merlin Games
(PDF) (Courtesy of Gregory Dennis. Used with permission.)

Scribe: Gregory Dennis

Lecturer: Shanghua Teng

16Interactive proofs of graph non-isomorphism(PDF) (Courtesy of Paul Chang. Used with permission.)Scribe: Paul M. Chang

Lecturer: Daniel A. Spielman
17Recap 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
19Recall 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
20The Multilinearity Test (cont.)(PDF) (Courtesy of Jan Vondrák. Used with permission.)Scribe: Jan Vondrák

Lecturer: Daniel A. Spielman
21Approximating Max-Clique

Reducing Satisfiable Clauses in 3CNF
(PDF) (Courtesy of Hiroyoshi Iwashima. Used with permission.)Scribe: Hiro Iwashima

Lecturer: Daniel A. Spielman
22Derandomizing Logspace Computations(PDF)Lecturer: Daniel A. Spielman

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.