An Exponential Depth-Hierarchy Theorem for Constant-Depth Multilinear Circuits

We study the size blow-up that is necessary to convert an algebraic circuit of constant product-depth D+1 to one of product-depth D in the multilinear setting.

We show that for every constant $D \geq 1$, there is an explicit multilinear polynomial $P_D$ on $n$ variables that can be computed by a multilinear formula of product-depth $D+1$ and size $n$, but not by any multilinear circuit of product-depth $D$ and size less than $\exp(n^{a_D})$ where $a_D$ is some constant that depends on $D$.

This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who proved a quasipolynomial separation, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case$ D=1$.

I will outline the basic ideas behind the proof of this result.

Joint work with Suryajith Chillara (CSE IITB), Christian Engels (CSE IITB) and Nutan Limaye (CSE IITB).