Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Raghunath Tewari
NPTEL Co-ordinating Institute : IIT Kanpur
NPTEL Lecture Count : 41
NPTEL Course Size : 9.5 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
Lecture 1 - Introduction
Lecture 2 - NP Completeness
Lecture 3 - SAT is NP-complete
Lecture 4 - More on NP completeness
Lecture 5 - Hierarchy Theorems
Lecture 6 - Introduction to Space Complexity
Lecture 7 - Savitch’s Theorem
Lecture 8 - Immerman-Szelepscenyi Theorem
Lecture 9 - 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 - II
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