NOC:Computational Complexity

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