# Computational Complexity Theory

- Institution: IIT Kanpur
- Department: Computer Science and Engineering
- Teacher: Prof. Raghunath Tewari
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106104227)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106104227)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Lecture 1: Introduction](https://invisiblenetwork.ai/learn/nptel/106104227/94cc156f57a0) (Video)
2. [Lecture 2: NP Completeness](https://invisiblenetwork.ai/learn/nptel/106104227/0340710a15b9) (Video)
3. [Lecture 3: SAT is NP-complete](https://invisiblenetwork.ai/learn/nptel/106104227/f44c157b1090) (Video)
4. [Lecture 4: More on NP completeness](https://invisiblenetwork.ai/learn/nptel/106104227/42ac06f22ad1) (Video)
5. [Lecture 05: Hierarchy Theorems](https://invisiblenetwork.ai/learn/nptel/106104227/a996c70538db) (Video)
6. [Lecture 06: Introduction to Space Complexity](https://invisiblenetwork.ai/learn/nptel/106104227/b0bbfd939d88) (Video)
7. [Lecture 07: Savitch's Theorem](https://invisiblenetwork.ai/learn/nptel/106104227/d8185228bc6a) (Video)
8. [Lecture 08: Immerman-Szelepscenyi Theorem](https://invisiblenetwork.ai/learn/nptel/106104227/98c04b6a75b2) (Video)
9. [Lecture 09: Polynomial Hierarchy](https://invisiblenetwork.ai/learn/nptel/106104227/04021e5f7565) (Video)
10. [Lecture 10: A PSPACE Complete Problem](https://invisiblenetwork.ai/learn/nptel/106104227/a7b59b231b83) (Video)
11. [Lecture 11: More on Polynomial Hierarchy](https://invisiblenetwork.ai/learn/nptel/106104227/b69bcc8ca7a1) (Video)
12. [Lecture 12: Alternating Turing Machines](https://invisiblenetwork.ai/learn/nptel/106104227/8f366ff93f84) (Video)
13. [Lecture 13: Equivalence of Quantifier and Oracle Based Definitions of Polynomial Hierarchy](https://invisiblenetwork.ai/learn/nptel/106104227/bb6855853400) (Video)
14. [Lecture 14: Boolean Circuits](https://invisiblenetwork.ai/learn/nptel/106104227/aa529f08a92a) (Video)
15. [Lecture 15: Shannon's Theorem and Karp-Lipton-Sipser Theorem](https://invisiblenetwork.ai/learn/nptel/106104227/130f9e7e0362) (Video)
16. [Lecture 16: Bounded Depth Circuit Classes](https://invisiblenetwork.ai/learn/nptel/106104227/e2986e24d33f) (Video)
17. [Lecture 17: Kannan's Theorem](https://invisiblenetwork.ai/learn/nptel/106104227/69fff39c5845) (Video)
18. [Lecture 18: Probabilistic Complexity](https://invisiblenetwork.ai/learn/nptel/106104227/7ec42510112d) (Video)
19. [Lecture 19: StrongBPP and WeakBPP](https://invisiblenetwork.ai/learn/nptel/106104227/e8b52574502d) (Video)
20. [Lecture 20: One-sided and Zero-sided Error Probabilistic Complexity Classes](https://invisiblenetwork.ai/learn/nptel/106104227/94dc97bb377b) (Video)
21. [Lecture 21: Error Reduction for BPP](https://invisiblenetwork.ai/learn/nptel/106104227/4c80a3404ea5) (Video)
22. [Lecture 22: BPP in PH and Logspace Randomized Classes](https://invisiblenetwork.ai/learn/nptel/106104227/9dbcd530f664) (Video)
23. [Lecture 23: Valiant-Vazirani Theorem - I](https://invisiblenetwork.ai/learn/nptel/106104227/3841f80e7038) (Video)
24. [Lecture 24: Valiant-Vazirani Theorem - I](https://invisiblenetwork.ai/learn/nptel/106104227/e0a396a2a386) (Video)
25. [Lecture 25: Amplified version of Valiant-Vazirani Theorem](https://invisiblenetwork.ai/learn/nptel/106104227/4d3e33e60adf) (Video)
26. [Lecture 26: Toda's Theorem - I](https://invisiblenetwork.ai/learn/nptel/106104227/ace43793abbe) (Video)
27. [Lecture 27: Toda's Theorem - II](https://invisiblenetwork.ai/learn/nptel/106104227/ae244dce65f6) (Video)
28. [Lecture 28: Permanent and Determinant Functions](https://invisiblenetwork.ai/learn/nptel/106104227/34b15dd298d5) (Video)
29. [Lecture 29: Permanent is hard for #P](https://invisiblenetwork.ai/learn/nptel/106104227/362b5aee5a19) (Video)
30. [Lecture 30: Interactive Proofs](https://invisiblenetwork.ai/learn/nptel/106104227/2710381733d0) (Video)
31. [Lecture 31: Graph Non-Isomorphism is in IP\[2\]](https://invisiblenetwork.ai/learn/nptel/106104227/2389380f4175) (Video)
32. [Lecture 32: Set Lower Bound Protocol](https://invisiblenetwork.ai/learn/nptel/106104227/f747d3acb8fb) (Video)
33. [Lecture 33: MA is in AM](https://invisiblenetwork.ai/learn/nptel/106104227/dda16087952c) (Video)
34. [Lecture 34: Sumcheck Protocol - I](https://invisiblenetwork.ai/learn/nptel/106104227/9b01c415907e) (Video)
35. [Lecture 35: Sumcheck Protocol - II](https://invisiblenetwork.ai/learn/nptel/106104227/901b3b75b5f3) (Video)
36. [Lecture 36: Parity not in AC0 - I](https://invisiblenetwork.ai/learn/nptel/106104227/75a0c15f5709) (Video)
37. [Lecture 37: Parity not in AC0 - II](https://invisiblenetwork.ai/learn/nptel/106104227/caa6cf50e703) (Video)
38. [Lecture 38 : Circuits with Counters](https://invisiblenetwork.ai/learn/nptel/106104227/fd243c6a3599) (Video)
39. [Lecture 39 : Communication Complexity - I](https://invisiblenetwork.ai/learn/nptel/106104227/0ce56960be49) (Video)
40. [Lecture 40 : PCP Theorem](https://invisiblenetwork.ai/learn/nptel/106104227/0d528cdaee72) (Video)
41. [Lecture 41 : Communication Complexity - II](https://invisiblenetwork.ai/learn/nptel/106104227/9a84e704662a) (Video)