Learn · NPTEL

Course10610424160 lectures

Circuit Complexity Theory

Prof. Raghunath Tewari · IIT Kanpur

Start with lecture 1 At NPTEL

Lectures

week-01

  1. Lecture 01: Introduction I Video
  2. Lecture 02: Introduction II Video
  3. Lecture 03: Lower bound for circuits Video
  4. Lecture 04: Lower bound for formulas Video
  5. Lecture 05: Khrapchenko's theorem Video

week-02

  1. Lecture 06: Proof of Khrapchenko's Theorem Video
  2. Lecture 07: Applications of Khrapchenko's Theorem Video
  3. Lecture 08: Nechiporuk's Theorem Video
  4. Lecture 09: Applications of Nechiporuk's Theorem Video
  5. Lecture 10: Subbotovskaya's Theorem I Video

week-03

  1. Lecture 11: Subbotovskaya's Theorem II Video
  2. Lecture 12: Applications of Subbotovskaya's Theorem Video
  3. Lecture 13: Upper and Lower Bounds on the Andreev Function Video
  4. Lecture 14: Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) I Video
  5. Lecture 15: Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) II Video

week-04

  1. Lecture 16: Circuits for Addition Ripple Adder and Carry Lookahead Adder Video
  2. Lecture 17: Circuits for Addition Parallel Prefix Sum Method Video
  3. Lecture 18: Circuits for Iterated Addition and Multiplication Video
  4. Lecture 19: Bounded Depth Circuit Classes Video
  5. Lecture 20: Basic Circuit for Division using NewtonRaphson Method Video

week-05

  1. Lecture 21: Division in NC1 (Beame, Cook, Hoover Theorem) I Video
  2. Lecture 22: Division in NC1 (Beame, Cook, Hoover Theorem) II Video
  3. Lecture 23: Division in NC1 (Beame, Cook, Hoover Theorem) III Video
  4. Lecture 24: Division in NC1 (Beame, Cook, Hoover Theorem) IV Video
  5. Lecture 25: Division in NC1 (Beame, Cook, Hoover Theorem) V Video

week-06

  1. Lecture 26: Division in NC1 (Beame, Cook, Hoover Theorem) VI Video
  2. Lecture 27: Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes I Video
  3. Lecture 28: Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes II Video
  4. Lecture 29: Reducing Circuit Depth Video
  5. Lecture 30: P is in P/poly Video

week-07

  1. Lecture 31: Discussion on Circuit Lower Bounds for Bounded Depth Circuit Classes Video
  2. Lecture 32: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) I Video
  3. Lecture 33: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) II Video
  4. Lecture 34: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) III Video
  5. Lecture 35: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) IV Video

week-08

  1. Lecture 36: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) V Video
  2. Lecture 37: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) VI Video
  3. Lecture 38: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) I Video
  4. Lecture 39: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) II Video
  5. Lecture 40: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) III Video

week-09

  1. Lecture 41: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) I Video
  2. Lecture 42: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) II Video
  3. Lecture 43: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) III Video
  4. Lecture 44: Proof of Hastad's Switching Lemma I Video
  5. Lecture 45: Proof of Hastad's Switching Lemma II Video

week-10

  1. Lecture 46: Communication Complexity of a Function Video
  2. Lecture 47: Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) I Video
  3. Lecture 48: Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) II Video
  4. Lecture 49: Bounded Width Branching Programs = NC1 (Barrington's Theorem) I Video
  5. Lecture 50: Bounded Width Branching Programs = NC1 (Barrington's Theorem) II Video

week-11

  1. Lecture 51: Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) I Video
  2. Lecture 52: Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) II Video
  3. Lecture 53: Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) I Video
  4. Lecture 54: Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) II Video
  5. Lecture 55: ValiantVazirani Theorem I Video

week-12

  1. Lecture 56: ValiantVazirani Theorem II Video
  2. Lecture 57: Natural Proof Barrier (RazborovRudich Theorem) I Video
  3. Lecture 58: Natural Proof Barrier (RazborovRudich Theorem) II Video
  4. Lecture 59: Pseudorandom Function Generator by Goldreich, Goldwasser and Micali I Video
  5. Lecture 60: Pseudorandom Function Generator by Goldreich, Goldwasser and Micali 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