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.
One can ask if the methods of @cite_7 @cite_37 can be used to prove our result. @cite_37 prove their result by defining a suitable complexity measure for any polynomial @math , and show that this measure is small for any subexponential-sized @math circuit but large for some linear-sized @math circuit. In particular, this means that this measure needs to be changed to prove lower bounds for larger depth circuits. However, it is not clear how to modify this measure to take into account the product-depth of the circuit class. This is not a problem with the technique of Raz and Yehudayoff @cite_7 , which can indeed be used to prove exponential lower bounds on the sizes of small-depth circuits for computing certain polynomials. However, the polynomials used to witness the superpolynomial separation cannot give an exponential depth-hierarchy, for the reasons we now explain.
@cite_37 @cite_7
2295840581 2150144243
We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following: 1. There exists an explicit n-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) such that every ROABP computing it requires 2^ Omega(n) size. 2. Any multilinear depth three circuit computing IMM_ n,d (the iterated matrix multiplication polynomial formed by multiplying d, n * n symbolic matrices) has n^ Omega(d) size. IMM_ n,d can be easily computed by a poly(n,d) sized ROABP. 3. Further, the proof of 2 yields an exponential separation between multilinear depth four and multilinear depth three circuits: There is an explicit n-variate, degree d polynomial computable by a poly(n,d) sized multilinear depth four circuit such that any multilinear depth three circuit computing it has size n^ Omega(d) . This improves upon the quasi-polynomial separation result by Raz and Yehudayoff [2009] between these two models. The hard polynomial in 1 is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure used previously in Nisan [1991], Raz [2006,2009], Raz and Yehudayoff [2009], and Forbes and Shpilka [2013], while 2 is proved via a new adaptation of the dimension of the partial derivatives measure used by Nisan and Wigderson [1997]. Our lower bounds hold over any field. 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.