Computational Complexity

Por: Swayam . en: ,

Week-1: Introduction to the course, Review of NP Completeness, P vs NP, Cook-Levin Theorem
Week-2: Time Hierarchy Theorem, Polynomial Hierarchy, Introduction to Space Complexity
Week-3: Savitch’s Theorem, NL-Completeness, NL = coNL Week-4: PSPACE Completeness, Space Hierarchy Theorem, Baker-Gill-Solovay Theorem
Week-5: Randomized Complexity Classes, BPP is in polynomial hierarchy
Week-6:Nonuniform computation, Circuit Complexity
Week-7: Parity not in AC^0
Week-8: Karp-Lipton Theorem, Adleman’s Theorem, Polynomial Identity Testing, Isolation Lemma, Perfect Matching is in NC^2
Week-9: #P and #P Completeness. Permanent is #P Complete.
Week-10: Valiant Vazirani Theorem and Toda’s Theorem
Week-11: Communication Complexity, Monotone depth lower bound for matching
Week-12: Interactive Proofs.