License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.52
URN: urn:nbn:de:0030-drops-109963
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10996/
Ramya, C. ;
Rao, B. V. Raghavendra
Lower Bounds for Multilinear Order-Restricted ABPs
Abstract
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 {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 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 <=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 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 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 Order-Restricted ABPs}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {52:1--52:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-117-7},
ISSN = {1868-8969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10996},
URN = {urn:nbn:de:0030-drops-109963},
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 |
