Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Indian Institute of Technology Kanpur

Circuit Complexity Theory

Indian Institute of Technology Kanpur and NPTEL via Swayam

Overview

Prepare for a new career with $100 off Coursera Plus
Gear up for jobs in high-demand fields: data analytics, digital marketing, and more.
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.

Syllabus

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

Taught by

Prof. Raghunath Tewari

Tags

Reviews

Start your review of Circuit Complexity Theory

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.