A Near-Optimal Depth-Hierarchy theorem for Small-Depth Multilinear Circuits

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

We show that for every positive D = o(log n/log log n), 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 O(n), but not by any multilinear circuit of product-depth D and size less than exp(n^{Omega(1/D)}). This result is tight up to the constant implicit in the double exponent for all D= o(log n/log log n).

This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who prove a quasipolynomial separation for constant-depth multilinear circuits, and a result of Kayal, Nair andSaha (STACS 2016) who give an exponential separation in the case D = 1.

Our separating examples may be viewed as algebraic analogues of variants of the Graph Reachability problem studied by Chen, Oliveira, Servedio and Tan (STOC 2016), who used them to prove lower bounds for constant-depth \emph{Boolean} circuits.

This work is joint with Suryajith Chillara (IIT Bombay, CSE), Christian Engels (IIT Bombay, CSE), and Nutan Limaye (IIT Bombay, CSE).