Learn · Circuit Complexity Theory
Lecture 9 of 60week-02
Lecture 09: Applications of Nechiporuk's Theorem
Prof. Raghunath Tewari · IIT Kanpur
Credits and licence
- From
- Circuit Complexity Theory, IIT Kanpur (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Lecture 01: Introduction I
- Lecture 02: Introduction II
- Lecture 03: Lower bound for circuits
- Lecture 04: Lower bound for formulas
- Lecture 05: Khrapchenko's theorem
- Lecture 06: Proof of Khrapchenko's Theorem
- Lecture 07: Applications of Khrapchenko's Theorem
- Lecture 08: Nechiporuk's Theorem
- Lecture 09: Applications of Nechiporuk's Theorem
- Lecture 10: Subbotovskaya's Theorem I
- Lecture 11: Subbotovskaya's Theorem II
- Lecture 12: Applications of Subbotovskaya's Theorem
- Lecture 13: Upper and Lower Bounds on the Andreev Function
- Lecture 14: Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) I
- Lecture 15: Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) II
- Lecture 16: Circuits for Addition Ripple Adder and Carry Lookahead Adder
- Lecture 17: Circuits for Addition Parallel Prefix Sum Method
- Lecture 18: Circuits for Iterated Addition and Multiplication
- Lecture 19: Bounded Depth Circuit Classes
- Lecture 20: Basic Circuit for Division using NewtonRaphson Method
- Lecture 21: Division in NC1 (Beame, Cook, Hoover Theorem) I
- Lecture 22: Division in NC1 (Beame, Cook, Hoover Theorem) II
- Lecture 23: Division in NC1 (Beame, Cook, Hoover Theorem) III
- Lecture 24: Division in NC1 (Beame, Cook, Hoover Theorem) IV
- Lecture 25: Division in NC1 (Beame, Cook, Hoover Theorem) V
- Lecture 26: Division in NC1 (Beame, Cook, Hoover Theorem) VI
- Lecture 27: Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes I
- Lecture 28: Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes II
- Lecture 29: Reducing Circuit Depth
- Lecture 30: P is in P/poly
- Lecture 31: Discussion on Circuit Lower Bounds for Bounded Depth Circuit Classes
- Lecture 32: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) I
- Lecture 33: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) II
- Lecture 34: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) III
- Lecture 35: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) IV
- Lecture 36: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) V
- Lecture 37: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) VI
- Lecture 38: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) I
- Lecture 39: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) II
- Lecture 40: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) III
- Lecture 41: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) I
- Lecture 42: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) II
- Lecture 43: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) III
- Lecture 44: Proof of Hastad's Switching Lemma I
- Lecture 45: Proof of Hastad's Switching Lemma II
- Lecture 46: Communication Complexity of a Function
- Lecture 47: Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) I
- Lecture 48: Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) II
- Lecture 49: Bounded Width Branching Programs = NC1 (Barrington's Theorem) I
- Lecture 50: Bounded Width Branching Programs = NC1 (Barrington's Theorem) II
- Lecture 51: Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) I
- Lecture 52: Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) II
- Lecture 53: Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) I
- Lecture 54: Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) II
- Lecture 55: ValiantVazirani Theorem I
- Lecture 56: ValiantVazirani Theorem II
- Lecture 57: Natural Proof Barrier (RazborovRudich Theorem) I
- Lecture 58: Natural Proof Barrier (RazborovRudich Theorem) II
- Lecture 59: Pseudorandom Function Generator by Goldreich, Goldwasser and Micali I
- Lecture 60: Pseudorandom Function Generator by Goldreich, Goldwasser and Micali II