IIT Kanpur · Computer Science

Circuit Complexity Theory

Prof. Raghunath Tewari · 60 free video lectures

60 video lectures. Topics: Introduction I; Introduction II; Lower bound for circuits; Lower bound for formulas; Khrapchenko's theorem; Proof of Khrapchenko's Theorem; Applications of Khrapchenko's Theorem; Nechiporuk's Theorem; Applications of Nechiporuk's Theorem; Subbotovskaya's Theorem I…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 01: Introduction I
  2. Lecture 02: Introduction II
  3. Lecture 03: Lower bound for circuits
  4. Lecture 04: Lower bound for formulas
  5. Lecture 05: Khrapchenko's theorem
  6. Lecture 06: Proof of Khrapchenko's Theorem
  7. Lecture 07: Applications of Khrapchenko's Theorem
  8. Lecture 08: Nechiporuk's Theorem
  9. Lecture 09: Applications of Nechiporuk's Theorem
  10. Lecture 10: Subbotovskaya's Theorem I
  11. Lecture 11: Subbotovskaya's Theorem II
  12. Lecture 12: Applications of Subbotovskaya's Theorem
  13. Lecture 13: Upper and Lower Bounds on the Andreev Function
  14. Lecture 14: Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) I
  15. Lecture 15: Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) II
  16. Lecture 16: Circuits for Addition Ripple Adder and Carry Lookahead Adder
  17. Lecture 17: Circuits for Addition Parallel Prefix Sum Method
  18. Lecture 18: Circuits for Iterated Addition and Multiplication
  19. Lecture 19: Bounded Depth Circuit Classes
  20. Lecture 20: Basic Circuit for Division using NewtonRaphson Method
  21. Lecture 21: Division in NC1 (Beame, Cook, Hoover Theorem) I
  22. Lecture 22: Division in NC1 (Beame, Cook, Hoover Theorem) II
  23. Lecture 23: Division in NC1 (Beame, Cook, Hoover Theorem) III
  24. Lecture 24: Division in NC1 (Beame, Cook, Hoover Theorem) IV
  25. Lecture 25: Division in NC1 (Beame, Cook, Hoover Theorem) V
  26. Lecture 26: Division in NC1 (Beame, Cook, Hoover Theorem) VI
  27. Lecture 27: Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes I
  28. Lecture 28: Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes II
  29. Lecture 29: Reducing Circuit Depth
  30. Lecture 30: P is in P/poly
  31. Lecture 31: Discussion on Circuit Lower Bounds for Bounded Depth Circuit Classes
  32. Lecture 32: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) I
  33. Lecture 33: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) II
  34. Lecture 34: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) III
  35. Lecture 35: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) IV
  36. Lecture 36: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) V
  37. Lecture 37: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) VI
  38. Lecture 38: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) I
  39. Lecture 39: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) II
  40. Lecture 40: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) III
  41. Lecture 41: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) I
  42. Lecture 42: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) II
  43. Lecture 43: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) III
  44. Lecture 44: Proof of Hastad's Switching Lemma I
  45. Lecture 45: Proof of Hastad's Switching Lemma II
  46. Lecture 46: Communication Complexity of a Function
  47. Lecture 47: Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) I
  48. Lecture 48: Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) II
  49. Lecture 49: Bounded Width Branching Programs = NC1 (Barrington's Theorem) I
  50. Lecture 50: Bounded Width Branching Programs = NC1 (Barrington's Theorem) II
  51. Lecture 51: Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) I
  52. Lecture 52: Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) II
  53. Lecture 53: Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) I
  54. Lecture 54: Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) II
  55. Lecture 55: ValiantVazirani Theorem I
  56. Lecture 56: ValiantVazirani Theorem II
  57. Lecture 57: Natural Proof Barrier (RazborovRudich Theorem) I
  58. Lecture 58: Natural Proof Barrier (RazborovRudich Theorem) II
  59. Lecture 59: Pseudorandom Function Generator by Goldreich, Goldwasser and Micali I
  60. Lecture 60: Pseudorandom Function Generator by Goldreich, Goldwasser and Micali II

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kanpur.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights