Accueil
Connexion
DENIF –
Documents d’Enseignement Numériques en Informatique Fondamentale
Thèmes
Cursus
Enseignants
Advanced Complexity Theory
Thème :
Complexité
–
Cursus :
MIT
Fall 2001
Instructor: Prof. Daniel Spielman.
Lecture Notes
Instructor: Prof. Daniel Spielman. With courtesy of scribes.
Course OverviewReview. P-Completeness and the Circuit Value Problem (CVP)
Alternation. Relations to Deterministic Classes
Polynomial Hierarchy
Polynomial Hierarchy (cont.). The Polynomial Time Hierarchy Collapses. Non-Uniform Complexity
NP and P/poly. Circuit Complexity
Relativization, The Baker-Gill-Solovay Theorem. Randomized Computation
BPP Error Amplification. Verifying Polynomial Identities
BPP Error Amplification Verifying Polynomial Identities - handout
The Valiant-Vazirani Theorem. Universal Hash Functions
Counting Classes. Toda's Theorem
Quantum Computation
Quantum Complexity
Fourier Transform. Discrete Log Problem. Calculable Quantum Fourier Transforms. Sufficiency of these Transforms
Oracle Quantum Turing Machines
Reusing Random Bits for BPP Algorithms: Definitions, Analysis
Interactive Proofs. Zero-Knowledge Proofs. Arthur-Merlin Games
Interactive proofs of graph non-isomorphism
Recap of Arthur-Merlin Games. Graph Isomorphism. Probabilistically Checkable Proofs. 3SAT Approximation is NP-hard
#P included in IP. PSPACE included in IP
Recall Proof Strategy of PSPACE included in IP. Implicit Circuit Sat and the Proof Outline. Multilinear Polynomials. The Multilinearity Test
The Multilinearity Test (cont.)
Approximating Max-Clique. Reducing Satisfiable Clauses in 3CNF
Derandomizing Logspace Computations