We study the size blow-up that is necessary to convert an algebraic circuit of product-depth δ+1 to one of product-depth δ in the multilinear setting. We show that for every positive δ = δ(n) = o(log n log log n), there is an explicit multilinear polynomial P^(δ) on n variables that can be computed by a multilinear formula of product-depth δ+1 and size O(n), but not by any multilinear circuit of product-depth δ and size less than exp(n^Ω(1 δ)). This result is tight up to the constant implicit in the double exponent for all δ = 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 and Saha (STACS 2016) who give an exponential separation in the case δ = 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 Boolean circuits.
The depth-hierarchy theorem of @cite_7 is obtained via an exponential lower bound @math against product-depth @math circuits computing polynomials from a certain hard'' class @math of polynomials on @math variables. Importantly, these lower bounds are tight in the sense that there also exist product-depth @math circuits of size roughly @math computing polynomials from @math . Since @math is superpolynomially larger than @math we obtain a superpolynomial separation between circuits of product-depth @math and product-depth @math . However, since we cannot improve on either the upper bound of @math or the lower bound of @math for this class of polynomials, we cannot hope to improve this separation.
@cite_7
2150144243
We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth d and product-depth d+1 multilinear circuits (where d is constant). That is, there exists a polynomial f such that (1) There exists a multilinear circuit of product-depth d+1 and of polynomial size computing f and (2) Every multilinear circuit of product-depth d computing f has super-polynomial size.