Lower bounds for multilinear order-restricted ABPs

Proving super-polynomial lower bounds on the size of syntactic multilinear Algebraic Branching Programs (smABPs) computing an explicit polynomial is a challenging problem in Algebraic Complexity Theory. The order in which variables in {x1, . . ., xn} appear along any source to sink path in an smABP can be viewed as a permutation in Sn. 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: 1. Strict circular-interval ABPs: For every sub-program the index set of variables occurring in it is contained in some circular interval of {1, . . ., n}. 2. L-ordered ABPs: There is a set of L permutations (orders) of variables such that every source to sink path in the smABP reads variables in one of these L orders, where L ≤ 2n1/2−ε for some ε > 0. We prove exponential (i.e., 2Ω(nδ), δ > 0) lower bounds on the size of above models computing an explicit multilinear 2n-variate polynomial in VP. As a main ingredient in our lower bounds, we show that any polynomial that can be computed 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 show that any size S syntactic multilinear ABP can be transformed into a size SO(✓n) depth four syntactic multilinear ΣΠΣΠ circuit where the bottom Σ gates compute polynomials on at most O(✓n) variables. Finally, we compare the above models with other standard models for computing multilinear polynomials.