Circuit Complexity Theory

ABOUT THE COURSE: This is a course on Boolean Circuit Complexity. In this course we study the Boolean circuit model of computation. We prove upper and lower bounds on circuit resources such as depth and size. The course is entirely mathematical, and a good level of mathematical maturity is essential. Prior knowledge of discrete mathematics, probability and basic algebra are prerequisites for this course. The course is intended for students who wish to pursue research in theoretical computer science. INTENDED AUDIENCE: Computer Science advanced undergraduate and postgraduate student interested in theoretical computer sciencePREREQUISITES: Basic undergraduate course in Theory of Computation and Algorithms. Undergraduate algebra and discrete mathematics.

Week 1: Boolean functions, circuits, formula, Shannon's Theorem, Riordon-Shannon TheoremWeek 2:Khrapchenko's Theorem and its applications, Nechiporuk's Theorem, Random RestrictionWeek 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, divisionWeek 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 circuitsWeek 7:Method of approximations, monotone lower bound on cliques of small sizeWeek 8:Monotone lower bound on cliques of arbitrary sizeWeek 9:Razborov-Smolensky lower bound for parityWeek 10:Lower bound for parity using Hastad's Switching LemmaWeek 11:Communication complexity and its relation to circuit complexity, Karchmer-Wigderson TheoremWeek 12:Recent advances in circuit lower bounds