Search Colleges, Exams, Schools & more
Login
Circuit Complexity Theory
Online
12 Weeks
Free Quick Facts
| Medium Of Instructions | Mode Of Learning | Mode Of Delivery |
|---|---|---|
| English | Self Study | Video and Text Based |
Courses and Certificate Fees
| Certificate Availability | Certificate Providing Authority |
|---|---|
| yes | IIT Kanpur |
The Syllabus
- 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
- Subbotovskaya's Theorem II
- Applications of Subbotovskaya's Theorem
- Upper and Lower Bounds on the Andreev Function
- Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) I
- Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) II
- Circuits for Addition Ripple Adder and Carry Lookahead Adder
- Circuits for Addition Parallel Prefix Sum Method
- Circuits for Iterated Addition and Multiplication
- Bounded Depth Circuit Classes
- Basic Circuit for Division using NewtonRaphson Method
- Division in NC1 (Beame, Cook, Hoover Theorem) I
- Division in NC1 (Beame, Cook, Hoover Theorem) II
- Division in NC1 (Beame, Cook, Hoover Theorem) III
- Division in NC1 (Beame, Cook, Hoover Theorem) IV
- Division in NC1 (Beame, Cook, Hoover Theorem) V
- Division in NC1 (Beame, Cook, Hoover Theorem) VI
- Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes I
- Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes II
- Reducing Circuit Depth
- P is in P/poly
- Discussion on Circuit Lower Bounds for Bounded Depth Circuit Classes
- Monotone Circuit Lower Bound for Clique (Razborov's Theorem) I
- Monotone Circuit Lower Bound for Clique (Razborov's Theorem) II
- Monotone Circuit Lower Bound for Clique (Razborov's Theorem) III
- Monotone Circuit Lower Bound for Clique (Razborov's Theorem) IV
- Monotone Circuit Lower Bound for Clique (Razborov's Theorem) V
- Monotone Circuit Lower Bound for Clique (Razborov's Theorem) VI
- Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) I
- Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) II
- Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) III
- Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) I
- Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) II
- Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) III
- Proof of Hastad's Switching Lemma I
- Proof of Hastad's Switching Lemma II
- Communication Complexity of a Function
- Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) I
- Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) II
- Bounded Width Branching Programs = NC1 (Barrington's Theorem) I
- Bounded Width Branching Programs = NC1 (Barrington's Theorem) II
- Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) I
- Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) II
- Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) I
- Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) II
- ValiantVazirani Theorem I
- ValiantVazirani Theorem II
- Natural Proof Barrier (RazborovRudich Theorem) I
- Natural Proof Barrier (RazborovRudich Theorem) II
- Pseudorandom Function Generator by Goldreich, Goldwasser and Micali I
- Pseudorandom Function Generator by Goldreich, Goldwasser and Micali II