Abstract
Proving superpolynomial 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 {x_1,...,x_n} appear along any source to sink path in an 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:
1) Strict circularinterval ABPs: For every subprogram the index set of variables occurring in it is contained in some circular interval of {1,..., n}.
2) Lordered 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 <=2^{n^{1/2 epsilon}} for some epsilon>0.
We prove exponential (i.e., 2^{Omega(n^delta)}, delta>0) lower bounds on the size of above models computing an explicit multilinear 2nvariate 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 S^{O(sqrt{n})} depth four syntactic multilinear Sigma Pi Sigma Pi circuit where the bottom Sigma gates compute polynomials on at most O(sqrt{n}) variables.
Finally, we compare the above models with other standard models for computing multilinear polynomials.
BibTeX  Entry
@InProceedings{ramya_et_al:LIPIcs:2019:10996,
author = {C. Ramya and B. V. Raghavendra Rao},
title = {{Lower Bounds for Multilinear OrderRestricted ABPs}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {52:152:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10996},
URN = {urn:nbn:de:0030drops109963},
doi = {10.4230/LIPIcs.MFCS.2019.52},
annote = {Keywords: Computational complexity, Algebraic complexity theory, Polynomials}
}
Keywords: 

Computational complexity, Algebraic complexity theory, Polynomials 
Collection: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) 
Issue Date: 

2019 
Date of publication: 

20.08.2019 