Changelog : Title was updated from "Advanced Complexity Theory" to the current one on Jul 2016.
Course Syllabus
- Circuit Complexity and Lower Bounds - Review of P/poly, Boolean Circuits, Basic circuit design and complexity classes. Decision trees, Branching Programs, Uniformity, Basic containments and Simulations - Parity is not in AC^0 - three different proofs, Monotone circuit lower bounds, Power of negations in circuits. Algebraic Complexity.
- Hardness vs Randomness - Derandomization Problem, PRGs, Extractors, Circuit lower bounds from PRGs, Nisan-Wigderson Generator, From worst case to average case, PRGs from hard functions.
- Arithmetic Circuits and Lower Bounds - The model, VP vs VNP question, completeness for the permanent. Identity testing vs Lower Bounds. Depth reductions. Chasm at depth 4. Mutilinearity. Partial derivatives method. Lower Bounds against depth 4 circuits.
- (Optional) Probabilistic Proof Systems -
Interactive Proofs, Arithemetization, IP=PSPACE, PCPs, inapproximability, Linearity testing, PCP theorem, Dinur's Combinatorial Proof.
References
