Learn · NPTEL

Course10610422741 lectures

Computational Complexity Theory

Prof. Raghunath Tewari · IIT Kanpur

Start with lecture 1 At NPTEL

Lectures

Week 1

  1. Lecture 1: Introduction Video
  2. Lecture 2: NP Completeness Video
  3. Lecture 3: SAT is NP-complete Video
  4. Lecture 4: More on NP completeness Video

Week 2

  1. Lecture 05: Hierarchy Theorems Video
  2. Lecture 06: Introduction to Space Complexity Video
  3. Lecture 07: Savitch's Theorem Video

Week 3

  1. Lecture 08: Immerman-Szelepscenyi Theorem Video
  2. Lecture 09: Polynomial Hierarchy Video
  3. Lecture 10: A PSPACE Complete Problem Video

Week 4

  1. Lecture 11: More on Polynomial Hierarchy Video
  2. Lecture 12: Alternating Turing Machines Video
  3. Lecture 13: Equivalence of Quantifier and Oracle Based Definitions of Polynomial Hierarchy Video

week 5

  1. Lecture 14: Boolean Circuits Video
  2. Lecture 15: Shannon's Theorem and Karp-Lipton-Sipser Theorem Video
  3. Lecture 16: Bounded Depth Circuit Classes Video

week 6

  1. Lecture 17: Kannan's Theorem Video
  2. Lecture 18: Probabilistic Complexity Video
  3. Lecture 19: StrongBPP and WeakBPP Video
  4. Lecture 20: One-sided and Zero-sided Error Probabilistic Complexity Classes Video

Week 7

  1. Lecture 21: Error Reduction for BPP Video
  2. Lecture 22: BPP in PH and Logspace Randomized Classes Video
  3. Lecture 23: Valiant-Vazirani Theorem - I Video

Week 8

  1. Lecture 24: Valiant-Vazirani Theorem - I Video
  2. Lecture 25: Amplified version of Valiant-Vazirani Theorem Video
  3. Lecture 26: Toda's Theorem - I Video
  4. Lecture 27: Toda's Theorem - II Video

week 9

  1. Lecture 28: Permanent and Determinant Functions Video
  2. Lecture 29: Permanent is hard for #P Video
  3. Lecture 30: Interactive Proofs Video

Week 10

  1. Lecture 31: Graph Non-Isomorphism is in IP[2] Video
  2. Lecture 32: Set Lower Bound Protocol Video
  3. Lecture 33: MA is in AM Video

Week 11

  1. Lecture 34: Sumcheck Protocol - I Video
  2. Lecture 35: Sumcheck Protocol - II Video
  3. Lecture 36: Parity not in AC0 - I Video
  4. Lecture 37: Parity not in AC0 - II Video

Week 12

  1. Lecture 38 : Circuits with Counters Video
  2. Lecture 39 : Communication Complexity - I Video
  3. Lecture 40 : PCP Theorem Video
  4. Lecture 41 : Communication Complexity - II Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kanpur
Department
Computer Science and Engineering
Teacher
Prof. Raghunath Tewari
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed