On the Structure and Lower Bounds for Multilinear Branching Programs

Abstract: Polynomials are the most fundamental mathematical objects in algebra and it is compelling to understand the complexity of computing polynomials. That is, given a polynomial we want to understand the number of arithmetic operations needed to compute it. Leslie G. Valiant introduced the notion of arithmetic circuits as a model for  computing polynomials. We will primarily be interested in size of an arithmetic circuit computing f which is the number of arithmetic operations needed to compute the polynomial f.  Further, Valiant conjectured that the permanent of an nxn matrix viewed as a polynomial cannot be computed by arithmetic circuits  of size polynomial in n. Subsequent to Valiant's conjecture, proving size  lower bounds for circuits computing permanent have been of much interest. While the answer to Valiant's conjecture seems to be at a distance, the focus has been on restricted classes of circuits.

In this talk, we will focus on Algebraic Branching Programs, yet another model for computing polynomials. Interesting polynomial families such as determinant, permanent etc. being multilinear, it is natural to consider syntactic multilinear Algebraic Branching Programs(smABPs) where every variable appears as an edge label at most once along any path in the branching program. The best known size lower bound for smABPs is barely quadratic in the number of variables. Proving super-polynomial size lower bounds for smABPs computing an explicit multilinear polynomial is a challenging problem in Algebraic Complexity Theory.

In this talk, we aim to understand the structure of smABPs and outline possible approaches to prove super-polynomial lower bounds for smABPs. We obtain a new decomposition theorem  for  smABPs: We show that  any n-variate 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 an immediate corollary to our decomposition theorem for smABPs, we obtain a low bottom fan-in version of the depth reduction by Tavenas[MFCS, 2013] for the case of smABPs.  This also leaves us with certain structural observations on smABPs which may be exploited to obtain super-polynomial lower bounds for smABPs. This is joint work with B.V.Raghavendra Rao, IIT Madras.