Courses:

Advanced Complexity Theory >> Content Detail



Calendar / Schedule



Calendar

LEC #TOPICSKEY DATES
1Course Overview

Review

P-Completeness and the Circuit Value Problem (CVP)
2Alternation

Relations to Deterministic Classes
3Polynomial Hierarchy
4Polynomial Hierarchy (cont.)

The Polynomial Time Hierarchy Collapses

Non-Uniform Complexity
5NP and P/poly

Circuit Complexity
6Relativization, The Baker-Gill-Solovay Theorem

Randomized Computation
7BPP Error Amplification

Verifying Polynomial Identities
8The Valiant-Vazirani Theorem

Universal Hash Functions
9Counting Classes

Toda's Theorem
10Quantum Computation
11Quantum ComplexityProblem set 1 due
12Fourier Transform

Discrete Log Problem

Calculable Quantum Fourier Transforms

Sufficiency of these Transforms
13Oracle Quantum Turing Machines
14Reusing Random Bits for BPP Algorithms: Definitions, Analysis
15Interactive Proofs

Zero-Knowledge Proofs

Arthur-Merlin Games
16Interactive proofs of graph non-isomorphism
17Recap of Arthur-Merlin Games

Graph Isomorphism

Probabilistically Checkable Proofs

3SAT Approximation is NP-hard
Problem set 2 due
18#P ⊆ IP

PSPACE ⊆ IP
19Recall Proof Strategy of PSPACE ⊆ IP

Implicit Circuit Sat and the Proof Outline

Multilinear Polynomials

The Multilinearity Test
20The Multilinearity Test (cont.)Problem set 3 due before next lecture
21Approximating Max-Clique

Reducing Satisfiable Clauses in 3CNF
22Derandomizing Logspace ComputationsProblem set 4 due (a week after this lecture)

 








© 2009-2020 HigherEdSpace.com, All Rights Reserved.
Higher Ed Space ® is a registered trademark of AmeriCareers LLC.