Monotone Circuit Lower Bounds from Robust Sunflowers

Bruno Pasqualotto Cavalar

Monotone Boolean circuits form one of the largest natural circuit classes for which we are able to prove exponential size lower bounds. Such lower bounds play a pivotal role in complexity theory, being a proxy for lower bounds on communication complexity, proof complexity and optimization. For over 20 years, the best known lower bound on the size of monotone circuits computing an explicit $n$-bit monotone Boolean function was $\exp(n^{1/3-o(1)})$. In this talk, we will motivate the study of monotone circuits and their applications, and present the first lower bound for monotone circuit size of order $\exp(n^{1/2-o(1)})$. The proof employs the classical approximation method of Razborov (1985) and recent robust sunflower bounds (Alweiss, Lovett, Wu, Zhang 2020 and Rao 2020). The presentation will be self-contained, and directions for further work will also be discussed.

 Overview  Program