Lower bounds for multilinear bounded order ABPs
share
Proving super-polynomial size lower bounds for syntactic multilinear Algebraic Branching Programs(smABPs) computing an explicit polynomial is a challenging problem in Algebraic Complexity Theory. The order in which variables in {x_1,...,x_n} appear along source to sink paths in any smABP can be viewed as a permutation in S_n. In this article, we consider the following special classes of smABPs where the order of occurrence of variables along a source to sink path is restricted: Strict circular-interval ABPs: For every subprogram the index set of variables occurring in it is contained in some circular interval of {1,...,n}. L-ordered ABPs: There is a set of L permutations of variables such that every source to sink path in the ABP reads variables in one of the L orders. We prove exponential lower bound for the size of a strict circular-interval ABP computing an explicit n-variate multilinear polynomial in VP. For the same polynomial, we show that any sum of L-ordered ABPs of small size will require exponential (2^n^Ω(1)) many summands, when L ≤ 2^n^1/2-ϵ, ϵ>0. At the heart of above lower bound arguments is a new decomposition theorem for smABPs: We show that any polynomial computable by an smABP of size S can be written as a sum of O(S) many multilinear polynomials where each summand is a product of two polynomials in at most 2n/3 variables computable by smABPs. As a corollary, we obtain a low bottom fan-in version of the depth reduction by Tavenas [MFCS 2013] in the case of smABPs. In particular, we show that a polynomial having size S smABPs can be expressed as a sum of products of multilinear polynomials on O(√(n)) variables, where the total number of summands is bounded by 2^O(√(n) n S). Additionally, we show that L-ordered ABPs can be transformed into L-pass smABPs with a polynomial blowup in size.
READ FULL TEXT