BARC talk by Théo Borém Fabris

Negations are powerful even in small depth

Abstract:
In arithmetic and Boolean circuit complexity, it is not known how to prove superpolynomial (in fact even quadratic) lower bounds for the size of general circuits computing explicit functions. Thus, it is natural to study the power and limitations of circuit models with structural restrictions, such as circuits with depth at most a constant or circuits that are not allowed to use NOT gates, also called monotone circuits. For these restricted circuits, there are a few known techniques that can be used to prove superpolynomial lower bounds.

Once it is known how to prove lower bounds for a certain computational model M, it is natural to ask how M is related to another model C that we believe is stronger than M. In particular, we are interested in finding efficient simulations of circuits in C using restricted circuits in M, or ruling out the existence of such efficient simulations. It is worth noting that efficient simulations of stronger models using weaker models are one of the main technical tools used to prove lower bounds in algebraic circuit complexity.

In this talk, we will present recent results that rule out the possibility that small depth circuits can be simulated by exponentially large monotone circuits. More precisely, our main results are the following:

  1. There is an n-variate polynomial P computed by a depth-3 circuit of size O(n^3) such that any monotone algebraic circuit computing P has size at least exp(\Omega(n)).
  2. There is an n-variate Boolean function f computed by a circuit of depth O(log n)^2 and size poly(n) such that any monotone Boolean circuit computing f has size at least exp(n^{1/3}).

During this presentation, we will mainly focus on the techniques used for proving the first result, which is a reduction of our original problem to a multipartition communication complexity lower bound, and then we used an expander graph technique to 'lift' a two-party communication complexity lower bound to the multipartition setting. These techniques may also be of independent interest.

This is a joint work with Bruno Pasqualotto Cavalar, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff. The paper is available at https://eccc.weizmann.ac.il/report/2025/219/ .

Théo Borém Fabris Short Bio: 
Théo Borém Fabris is a PhD student affiliated to BARC and working under the supervision of Amir Yehudayoff and Srikanth Srinivasan. He is broadly interested in theoretical computer science and computational complexity. His personal website is https://theobf.github.io/.