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

  1. Lecture 1: Introduction
  2. Lecture 2: NP Completeness
  3. Lecture 3: SAT is NP-complete
  4. Lecture 4: More on NP completeness
  5. Lecture 05: Hierarchy Theorems
  6. Lecture 06: Introduction to Space Complexity
  7. Lecture 07: Savitch's Theorem
  8. Lecture 08: Immerman-Szelepscenyi Theorem
  9. Lecture 09: Polynomial Hierarchy
  10. Lecture 10: A PSPACE Complete Problem
  11. Lecture 11: More on Polynomial Hierarchy
  12. Lecture 12: Alternating Turing Machines
  13. Lecture 13: Equivalence of Quantifier and Oracle Based Definitions of Polynomial Hierarchy
  14. Lecture 14: Boolean Circuits
  15. Lecture 15: Shannon's Theorem and Karp-Lipton-Sipser Theorem
  16. Lecture 16: Bounded Depth Circuit Classes
  17. Lecture 17: Kannan's Theorem
  18. Lecture 18: Probabilistic Complexity
  19. Lecture 19: StrongBPP and WeakBPP
  20. Lecture 20: One-sided and Zero-sided Error Probabilistic Complexity Classes
  21. Lecture 21: Error Reduction for BPP
  22. Lecture 22: BPP in PH and Logspace Randomized Classes
  23. Lecture 23: Valiant-Vazirani Theorem - I
  24. Lecture 24: Valiant-Vazirani Theorem - I
  25. Lecture 25: Amplified version of Valiant-Vazirani Theorem
  26. Lecture 26: Toda's Theorem - I
  27. Lecture 27: Toda's Theorem - II
  28. Lecture 28: Permanent and Determinant Functions
  29. Lecture 29: Permanent is hard for #P
  30. Lecture 30: Interactive Proofs
  31. Lecture 31: Graph Non-Isomorphism is in IP[2]
  32. Lecture 32: Set Lower Bound Protocol
  33. Lecture 33: MA is in AM
  34. Lecture 34: Sumcheck Protocol - I
  35. Lecture 35: Sumcheck Protocol - II
  36. Lecture 36: Parity not in AC0 - I
  37. Lecture 37: Parity not in AC0 - II
  38. Lecture 38 : Circuits with Counters
  39. Lecture 39 : Communication Complexity - I
  40. Lecture 40 : PCP Theorem
  41. 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