IIT Kanpur · Computer Science
Computational Complexity Theory
Prof. Raghunath Tewari · 41 free video lectures
41 video lectures. Topics: Introduction; NP Completeness; SAT is NP-complete; More on NP completeness; Hierarchy Theorems; Introduction to Space Complexity; Savitch's Theorem; Immerman-Szelepscenyi Theorem; Polynomial Hierarchy; A PSPACE Complete Problem; More on Polynomial Hierarchy; Alternating…
▶ Play on Open Lecture HallCourse page ↗
Lectures
- Lecture 1: Introduction
- Lecture 2: NP Completeness
- Lecture 3: SAT is NP-complete
- Lecture 4: More on NP completeness
- Lecture 05: Hierarchy Theorems
- Lecture 06: Introduction to Space Complexity
- Lecture 07: Savitch's Theorem
- Lecture 08: Immerman-Szelepscenyi Theorem
- Lecture 09: Polynomial Hierarchy
- Lecture 10: A PSPACE Complete Problem
- Lecture 11: More on Polynomial Hierarchy
- Lecture 12: Alternating Turing Machines
- Lecture 13: Equivalence of Quantifier and Oracle Based Definitions of Polynomial Hierarchy
- Lecture 14: Boolean Circuits
- Lecture 15: Shannon's Theorem and Karp-Lipton-Sipser Theorem
- Lecture 16: Bounded Depth Circuit Classes
- Lecture 17: Kannan's Theorem
- Lecture 18: Probabilistic Complexity
- Lecture 19: StrongBPP and WeakBPP
- Lecture 20: One-sided and Zero-sided Error Probabilistic Complexity Classes
- Lecture 21: Error Reduction for BPP
- Lecture 22: BPP in PH and Logspace Randomized Classes
- Lecture 23: Valiant-Vazirani Theorem - I
- Lecture 24: Valiant-Vazirani Theorem - I
- Lecture 25: Amplified version of Valiant-Vazirani Theorem
- Lecture 26: Toda's Theorem - I
- Lecture 27: Toda's Theorem - II
- Lecture 28: Permanent and Determinant Functions
- Lecture 29: Permanent is hard for #P
- Lecture 30: Interactive Proofs
- Lecture 31: Graph Non-Isomorphism is in IP[2]
- Lecture 32: Set Lower Bound Protocol
- Lecture 33: MA is in AM
- Lecture 34: Sumcheck Protocol - I
- Lecture 35: Sumcheck Protocol - II
- Lecture 36: Parity not in AC0 - I
- Lecture 37: Parity not in AC0 - II
- Lecture 38 : Circuits with Counters
- Lecture 39 : Communication Complexity - I
- Lecture 40 : PCP Theorem
- Lecture 41 : Communication Complexity - II
From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kanpur.
Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights