Circuit Complexity Theory Course | Boolean Circuits, Lower Bounds, NC, AC | IIT Kanpur
Course Details
| Exam Registration | 6 |
|---|---|
| Course Status | Ongoing |
| Course Type | Elective |
| Language | English |
| Duration | 12 weeks |
| Categories | Computer Science and Engineering |
| Credit Points | 3 |
| Level | Undergraduate/Postgraduate |
| Start Date | 19 Jan 2026 |
| End Date | 10 Apr 2026 |
| Enrollment Ends | 02 Feb 2026 |
| Exam Registration Ends | 20 Feb 2026 |
| Exam Date | 24 Apr 2026 IST |
| NCrF Level | 4.5 — 8.0 |
Demystifying the Foundations of Computation: A Guide to Circuit Complexity Theory
For advanced students of computer science, the quest to understand the fundamental limits of computation leads to one of the field's most profound and challenging areas: Circuit Complexity Theory. This 12-week course, offered by Prof. Raghunath Tewari of IIT Kanpur, provides a rigorous mathematical journey into the Boolean circuit model, the bedrock upon which our understanding of efficient computation is built.
Course Overview: A Mathematical Expedition
This is not a course about programming languages or software engineering. It is a deeply mathematical exploration of the Boolean circuit model of computation. The primary objective is to answer a core question: What are the minimal resources—specifically circuit size and depth—required to compute specific functions?
You will learn to prove both upper bounds (showing a function *can* be computed with certain resources) and, more challengingly, lower bounds (proving that a function *cannot* be computed with fewer than a certain amount of resources). A high level of mathematical maturity and comfort with proof-based reasoning is essential for success.
Who Should Take This Course?
This course is specifically designed for:
- Advanced undergraduate and postgraduate students in Computer Science and Engineering.
- Individuals with a strong interest in theoretical computer science and computational complexity.
- Aspiring researchers aiming to contribute to the frontiers of complexity theory.
Essential Prerequisites
To fully engage with the material, students must have a solid foundation in:
- Theory of Computation (Automata, Turing Machines, NP-Completeness).
- Design and Analysis of Algorithms.
- Discrete Mathematics (Logic, Combinatorics, Graph Theory).
- Undergraduate Algebra.
- Probability.
Weekly Course Layout: A 12-Week Journey
| Week | Core Topics |
|---|---|
| Week 1-3 | Boolean functions, circuits, and formulas. Foundational lower bound techniques: Shannon's Theorem, Khrapchenko's Theorem, Nechiporuk's Theorem, and the method of Random Restriction. |
| Week 4-5 | Complexity of arithmetic operations. Introduction to parallel complexity classes: NC, AC, and TC. The Beame-Cook-Hoover Theorem on division in NC. |
| Week 6-7 | Connecting circuits to uniform models (Turing Machines). The Method of Approximations for proving monotone circuit lower bounds, starting with the clique function. |
| Week 8-9 | Advanced lower bounds: Continuation of monotone bounds, the Razborov-Smolensky lower bound for parity, and the powerful Hastad's Switching Lemma. |
| Week 10-11 | Connections to Communication Complexity (Karchmer-Wigderson Theorem). Equivalence results: Barrington's Theorem (bounded-width branching programs) and the Allender-Hertrampf Theorem. |
| Week 12 | Frontiers and barriers: The Valiant-Vazirani Theorem on unique SAT and the profound Natural Proof Barrier (Razborov-Rudich Theorem), explaining why proving strong lower bounds is so difficult. |
Why Study Circuit Complexity?
Circuit complexity is more than an academic exercise. It provides the most concrete model for studying the P vs. NP problem and other major questions in complexity theory. Understanding lower bounds helps us comprehend the intrinsic difficulty of problems, guiding algorithm design and revealing the limits of what is efficiently computable. This course equips you with the toolkit used by researchers to tackle these grand challenges.
Instructor Profile: Prof. Raghunath Tewari
The course is led by Prof. Raghunath Tewari, an Associate Professor in the Department of Computer Science and Engineering at IIT Kanpur. His research expertise in computational complexity theory, algorithms, and graph theory ensures that the instruction is both authoritative and informed by cutting-edge developments in the field.
If you are ready to move beyond applied computing and delve into the mathematical heart of what computation truly is—and what its ultimate limits might be—this course on Circuit Complexity Theory is your essential next step.
Enroll Now →