NOC:Computational Complexity Theory

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