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