Week 1: Boolean functions, circuits, formula, Shannon's Theorem, Riordon-Shannon Theorem
Week 2: Khrapchenko's Theorem and its applications, Nechiporuk's Theorem, Random Restriction
Week 3: Subbotovskaya's lower bound on formula size, Andreev function, Polynomial sized monotone formula for majority (Valiant's Theorem)
Week 4: Complexity of basic arithmetic operations - addition, multiplication, division
Week 5: Bounded depth circuits, the complexity classes, NC, AC and TC. Division, powering and iterated products in NC (Beame-Cook-Hoover Theorem)
Week 6: Uniform model of computation - Turing machines and its relationship with circuits
Week 7: Method of approximations, monotone lower bound on cliques.
Week 8: Monotone lower bound on cliques (contd.), Razborov-Smolensky lower bound for parity
Week 9: Lower bound for parity using Hastad's Switching Lemma
Week 10: Communication complexity and its relation to circuit complexity, Karchmer-Wigderson Theorem, Bounded width branching programs = NC1 (Barrington's Theorem)
Week 11: Circuit equivalence of width 3 branching programs (Barrington's Theorem), simulating AC0 using depth 3 threshold circuits (Allender-Hertramph Theorem)
Week 12: Valiant-Vazirani Theorem, Natural Proof Barrier (Razborov-Rudich Theorem)
DOWNLOAD APP
FOLLOW US