Circuit Complexity Theory
Online
12 WeeksQuick Facts
| Medium Of Instructions | Mode Of Learning | Mode Of Delivery |
|---|---|---|
| English | Self Study | Video and Text Based |
Important dates
Course Commencement Date
Start Date : 19 Jan, 2026
End Date : 10 Apr, 2026
Certificate Exam Date
End Date : 24 Apr, 2026
Courses and Certificate Fees
| Fees Informations | Certificate Availability | Certificate Providing Authority |
|---|---|---|
| INR 1000 | yes | IIT Kanpur |
The Syllabus
- Boolean functions, circuits, formula, Shannon's Theorem, Riordon-Shannon Theorem
Khrapchenko's Theorem and its applications, Nechiporuk's Theorem, Random Restriction
Subbotovskaya's lower bound on formula size, Andreev function, Polynomial sized monotone formula for majority (Valiant's Theorem)
Complexity of basic arithmetic operations - addition, multiplication, division
Bounded depth circuits, the complexity classes, NC, AC and TC. Division, powering and iterated products in NC (Beame-CookHoover Theorem)
Uniform model of computation - Turing machines and its relationship with circuits
Method of approximations, monotone lower bound on cliques of small size
Monotone lower bound on cliques of arbitrary size
Razborov-Smolensky lower bound for parity
Lower bound for parity using Hastad's Switching Lemma
Communication complexity and its relation to circuit complexity, Karchmer-Wigderson Theorem
Recent advances in circuit lower bounds