Monotone Circuit Lower Bounds

Title of the Talk: Monotone Circuit Lower Bounds
Speakers: Tameem
Host Faculty: Dr. Nitin Saurabh
Date: Sep 23, 2025
Time: 2:30 pm
Venue: CS - LH-1, EE/CS building

Abstract:
Proving P is not equal to NP is one of the most important problems in Computer Science and a key approach is to show super polynomial lower bounds on the size of Boolean circuits for problems in NP. Unfortunately the best known lower bounds for the general circuit for an explicit function is at most linear. However significant progress has been made in showing super polynomial lower bounds for restricted models. This talk focuses on one such model: Monotone circuits.

We will explore Alexander Razborov’s landmark proof that the clique problem which is a NP complete problem requires super polynomial sized monotone circuits. We will go through the technique used to establish the lower bound and will also discuss why such ideas are unlikely to resolve the P vs NP question for general circuits.

Bio:
Tameem is a research scholar at IIT-H CSE department supervised by Dr. Karteek Sreenivasaiah and Dr. Rakesh Venkat. His PhD Work focuses on showing unconditional fine grained lower bounds for functions in non-uniform models of computation. His broad research interests are in Computational Complexity and Fine grained Complexity.