IIT Hyderabad · Computer Science

Computational Complexity

Prof. Subrahmanyam Kalyanasundaram · 63 free video lectures

This course is an introduction to the area of computational complexity theory. We will see different models of computations and computational complexity classes. The computational models measure various different aspects of computation, like time, space, randomness, number of gates, amount of…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Introduction to Computational Complexity
  2. The Class P
  3. The Class NP
  4. The Class NP - Alternate Definition
  5. Polynomial Time Reductions
  6. NP - Completeness
  7. Cook Levin Theorem: Part 1
  8. Cook Levin Theorem: Part 2
  9. More NP Complete Problems
  10. Polynomial Hierarchy: Part 1
  11. Polynomial Hierarchy: Part 2
  12. Polynomial Hierarchy: Part 3
  13. Time Hierarchy Theorem
  14. Introduction to Space Complexity
  15. NL-Completeness
  16. Savitch's Theorem
  17. NL = co-NL: Part 1
  18. NL = co-NL: Part 2
  19. PSPACE Completeness
  20. Games and PSPACE Completeness
  21. Space Hierarchy Theorem
  22. Ladner's Theorem
  23. Oracle Turing Machines
  24. Polynomial Hierarchy Using Oracles
  25. Baker-Gill-Solovay Theorem: Part 1
  26. Baker-Gill-Solovay Theorem: Part 2
  27. Randomized Complexity Classes: Part 1
  28. Randomized Complexity Classes: Part 2
  29. Randomized Complexity Classes: Part 3
  30. Randomized Complexity Classes: Part 4
  31. Comparison Between Randomized Complexity Classes
  32. BPP is in Polynomial Hierarchy
  33. Circuit Complexity: Part 1
  34. Circuit Complexity: Part 2
  35. Formal Definition of Circuits
  36. Hierarchy Theorem for Circuit Size
  37. Complexity Class : P/Poly
  38. Karp-Lipton Theorem
  39. Turing Machines That Take Advice
  40. Classes NC and AC
  41. Parity Not in AC0: Part 1
  42. Parity Not in AC0: Part 2
  43. Adleman's Theorem
  44. Polynomial Identity Testing and Bipartite Perfect Matching in RNC
  45. Search Bipartite Perfect Matching is in RNC: Part 1
  46. Search Bipartite Perfect Matching is in RNC: Part 2
  47. Promise Problems and Valiant-Vazirani Theorem
  48. Valiant Vazirani Theorem Continued
  49. #P and the Complexity of Counting
  50. Permanent is #P-Complete: Part 1
  51. Permanent is #P-Complete: Part 2
  52. Toda's Theorem: Part 1
  53. Toda's Theorem: Part 2
  54. Introduction to Communication Complexity: Part 1
  55. Introduction to Communication Complexity: Part 2
  56. Lower Bound Techniques
  57. Communication Complexity of Relations
  58. Monotone Depth Lower Bound for Matching
  59. Interactive Proofs
  60. #3SAT is in IP
  61. Public Coin Interactive Proofs and AM/MA
  62. Simulating Private Coins using Public Coins
  63. Summary and Concluding Remarks

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Hyderabad.

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