Computational Complexity 

offered by IIT Hyderabad

Introduction to the course, Polynomial time reductions, P and NP classes, Review of NP Completeness, P vs NP

NP Complete problems, Cook-Levin Theorem, Polynomial Hierarchy

Time Hierarchy Theorem, Space Complexity, Savitch’s Theorem, NL-Completeness, NL = coNL

PSPACE Completeness, Space Hierarchy Theorem, Ladner Theorem, Oracles

Baker-Gill-Solovay Theorem, Randomized Complexity Classes

Randomized Complexity Classes(contd.), BPP is in polynomial hierarchy, Circuit Complexity

Circuit Hierarchy Theorem, P/poly complexity class, NC and AC classes, Karp-Lipton Theorem

Parity not in AC^0, Adleman’s Theorem, Polynomial Identity Testing, Perfect Matching is in RNC^2

Bipartite Perfect Matching is in RNC (contd.), Isolation Lemma, Valiant Vazirani Theorem, #P and #P Completeness.

Permanent is #P Complete, Toda’s Theorem

Communication Complexity, Lower bound techniques, Monotone depth lower bound for matching.

Introduction to Interactive Proofs, #3-SAT is in IP, Private and Public Coin Interactive proofs, Course summary.