mod01lec01 - Introduction to Computational Complexity

Preview 35:23

mod01lec02 - The Class P

Preview 27:04

mod01lec03 - The Class NP

Preview 41:14

mod01lec04 - The Class NP - Alternate Definition

Preview 39:06

mod01lec05 - Polynomial Time Reductions

Preview 43:04

mod01lec06 - NP - Completeness

Preview 12:00

mod02lec07 - Cook Levin Theorem: Part 1

Preview 36:35

mod02lec08 - Cook Levin Theorem: Part 2

Preview 33:25

mod02lec09 - More NP Complete Problems

Preview 35:49

mod02lec10 - Polynomial Hierarchy: Part 1

Preview 19:49

mod02lec11 - Polynomial Hierarchy: Part 2

Preview 35:22

mod02lec12 - Polynomial Hierarchy: Part 3

Preview 24:05

mod03lec13 - Time Hierarchy Theorem

Preview 36:07

mod03lec14 - Introduction to Space Complexity

Preview 42:21

mod03lec15 - NL-Completeness

Preview 36:23

mod03lec16 - Savitch's Theorem

Preview 28:23

mod03lec17 - NL = co-NL: Part 1

Preview 31:30

mod03lec18 - NL = co-NL: Part 2

Preview 26:09

mod04lec19 - PSPACE Completeness

Preview 46:26

mod04lec20 - Games and PSPACE Completeness

Preview 30:02

mod04lec21 - Space Hierarchy Theorem

Preview 32:56

mod04lec22 - Ladner's Theorem

Preview 20:30

mod04lec23 - Oracle Turing Machines

Preview 24:38

mod04lec24 - Polynomial Hierarchy Using Oracles

Preview 28:56

mod05lec25 - Baker-Gill-Solovay Theorem: Part 1

Preview 28:58

mod05lec26 - Baker-Gill-Solovay Theorem: Part 2

Preview 30:15

mod05lec27 - Randomized Complexity Classes: Part 1

Preview 35:01

mod05lec28 - Randomized Complexity Classes: Part 2

Preview 44:27

mod05lec29 - Randomized Complexity Classes: Part 3

Preview 38:22

mod06lec30 - Randomized Complexity Classes: Part 4

Preview 37:11

mod06lec31 - Comparison Between Randomized Complexity Classes

Preview 11:20

mod06lec32 - BPP is in Polynomial Hierarchy

Preview 44:25

mod06lec33 - Circuit Complexity: Part 1

Preview 33:17

mod06lec34 - Circuit Complexity: Part 2

Preview 30:11

mod07lec35 - Formal Definition of Circuits

Preview 28:39

mod07lec36 - Hierarchy Theorem for Circuit Size

Preview 29:43

mod07lec37 - Complexity Class : P/Poly

Preview 24:03

mod07lec38 - Karp-Lipton Theorem

Preview 51:59

mod07lec39 - Turing Machines That Take Advice

Preview 19:36

mod07lec40 - Classes NC and AC

Preview 48:00

mod08lec41 - Parity Not in AC0: Part 1

Preview 81:25

mod08lec42 - Parity Not in AC0: Part 2

Preview 42:17

mod08lec43 - Adleman's Theorem

Preview 15:19

mod08lec44 - Polynomial Identity Testing and Bipartite Perfect Matching in RNC

Preview 51:38

mod09lec45 - Search Bipartite Perfect Matching is in RNC: Part 1

Preview 24:28

mod09lec46 - Search Bipartite Perfect Matching is in RNC: Part 2

Preview 27:40

mod09lec47 - Promise Problems and Valiant-Vazirani Theorem

Preview 21:55

mod09lec48 - Valiant Vazirani Theorem Continued

Preview 55:14

mod09lec49 - #P and the Complexity of Counting

Preview 39:19

mod10lec50 - Permanent is #P-Complete: Part 1

Preview 65:10

mod10lec51 - Permanent is #P-Complete: Part 2

Preview 19:01

mod10lec52 - Toda's Theorem: Part 1

Preview 60:24

mod10lec53 - Toda's Theorem: Part 2

Preview 36:47

mod11 lec54 - Introduction to Communication Complexity: Part 1

Preview 40:01

mod11lec55 - Introduction to Communication Complexity: Part 2

Preview 47:51

mod11lec56 - Lower Bound Techniques

Preview 35:32

mod11lec57 - Communication Complexity of Relations

Preview 52:07

mod11lec58 - Monotone Depth Lower Bound for Matching

Preview 37:27

mod12lec59 - Interactive Proofs

Preview 44:51

mod12lec60 - #3SAT is in IP

Preview 62:13

mod12lec61 - Public Coin Interactive Proofs and AM/MA

Preview 49:15

mod12lec62 - Simulating Private Coins using Public Coins

Preview 34:38

mod12lec63 - Summary and Concluding Remarks

Preview 25:29

Live Session 30-07-2021

Preview 28:05

Live Session 08-06-2021

Preview 24:25

Live Session 08-10-2021

Preview 17:20