Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Raghunath Tewari
NPTEL Co-ordinating Institute : IIT Kanpur
NPTEL Lecture Count : 60
NPTEL Course Size : 11 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
Lecture 1 - Introduction
Lecture 2 - Standard Bounds
Lecture 3 - Shannon's Theorem
Lecture 4 - Riordon-Shannon Theorem
Lecture 5 - Khrapchenko's Theorem
Lecture 6 - Proof of Khrapchenko's Theorem
Lecture 7 - Application of Khrapchenko's Theorem
Lecture 8 - Nechiporuk's Theorem
Lecture 9 - Application 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 - Upper and Lower Bounds on the Andreev Function
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 Newton-Raphson 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 Lower Circuit 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 (Razborov-Smolensky Theorem) - I
Lecture 39 - Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (Razborov-Smolensky Theorem) - II
Lecture 40 - Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (Razborov-Smolensky Theorem) - III
Lecture 41 - Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem)
Lecture 42 - Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem)
Lecture 43 - Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem)
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 (Karchmer-Wigderson Theorem) - I
Lecture 48 - Relation Between Communication Complexity and Circuit Depth (Karchmer-Wigderson 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 (Allender-Hertramph Theorem) - I
Lecture 54 - Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (Allender-Hertramph Theorem) - II
Lecture 55 - Valient-Vazirani Theorem - I
Lecture 56 - Valient-Vazirani Theorem - II
Lecture 57 - Natural Proof Barrier (Razborov-Rudich Theorem) - I
Lecture 58 - Natural Proof Barrier (Razborov-Rudich Theorem) - II
Lecture 59 - Pseudorandom Function Generator by Goldreich, Goldwasser and Micali - I
Lecture 60 - Pseudorandom Function Generator by Goldreich, Goldwasser and Micali - II