On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models

Article type: Research Article

Authors: Ghosal, Purnata^{; *} | Raghavendra Rao, B.V.

Affiliations: Indian Institute of Technology Madras, Chennai, 600036 India. [email protected], [email protected]

Correspondence: [*] Address for correspondence: Indian Institute of Technology Madras, Chennai, 600036 India.

Abstract: We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. We consider the following special classes of multilinear algebraic branching programs: 1) Read Once Oblivious Branching Programs (ROABPs), 2) Strict interval branching programs, 3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., nΩ(t(k)) lower bound for some function t of k) on the size of the above models computing a multilinear polynomial that can be computed by a depth four circuit of size g(k)nO(1) for some computable function g. Further, we obtain a parameterized separation between ROABPs and read-2 ABPs. This is obtained by constructing a degree k polynomial that can be computed by a read-2 ABP of small size such that the rank of the partial derivative matrix under any partition of the variables is large.

DOI: 10.3233/FI-2020-1980

Journal: Fundamenta Informaticae, vol. 177, no. 1, pp. 69-93, 2020