CS6840 - Modern Complexity Theory

Course Data :

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.




Credits Type Date of Introduction
4-0-0-0-8-12 Elective Jan 2012

Previous Instances of the Course

© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits