2026-08-06T13:43:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10996 2024-03-06T10:47:00Z ddc:004 open_access

Lower Bounds for Multilinear Order-Restricted ABPs Ramya, C. Rao, B. V. Raghavendra Computational complexity Algebraic complexity theory Polynomials 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik C. Ramya and B. V. Raghavendra Rao 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.52 urn:nbn:de:0030-drops-109963 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.52 eng https://creativecommons.org/licenses/by/3.0/legalcode