Week 1: Introduction to the course, Polynomial time reductions, P and NP classes, Review of NP Completeness, P vs NP
Week 2: NP Complete problems, Cook-Levin Theorem, Polynomial Hierarchy
Week 3: Time Hierarchy Theorem, Space Complexity, Savitch’s Theorem, NL-Completeness, NL = coNL
Week 4: PSPACE Completeness, Space Hierarchy Theorem, Ladner Theorem, Oracles
Week 5: Baker-Gill-Solovay Theorem, Randomized Complexity Classes
Week 6: Randomized Complexity Classes(contd.), BPP is in polynomial hierarchy, Circuit Complexity
Week 7: Circuit Hierarchy Theorem, P/poly complexity class, NC and AC classes, Karp-Lipton Theorem
Week 8: Parity not in AC^0, Adleman’s Theorem, Polynomial Identity Testing, Perfect Matching is in RNC^2
Week 9: Bipartite Perfect Matching is in RNC (contd.), Isolation Lemma, Valiant Vazirani Theorem, #P and #P Completeness.
Week 10: Permanent is #P Complete, Toda’s Theorem
Week 11: Communication Complexity, Lower bound techniques, Monotone depth lower bound for matching.
Week 12: Introduction to Interactive Proofs, #3-SAT is in IP, Private and Public Coin Interactive proofs, Course summary.
DOWNLOAD APP
FOLLOW US