| Title | : | Lower Bounds for Special Classes of Syntactic Multilinear ABPs |
| Speaker | : | Ramya C. (IIT Madras) |
| Details | : | Wed, Jun 27, 2018 3:00 PM, @ Turing Hall |
| Abstract | : | Algebraic Branching Programs(ABPs) are edge-labelled layered directed acyclic graphs with a dedicated source node s and terminal node t
with edges labelled by variables or constants. The polynomial computed by an ABP is the sum over all s to t paths, product of edge labels in the corresponding path. ABPs are standard models for computing polynomials that have been studied time and again in the context of lower bounds and identity testing. While the challenge of proving super-polynomial lower bounds for Algebraic Branching Programs still seems to be a distant dream, naturally the focus has been on restricted classes of ABPs. Syntactic multilinear ABPs are restrictions of ABPs where every variable is allowed to occur at most once in every path from the source to terminal node. Proving lower bounds for syntactic multilinear ABPs remains a long-standing open question in Algebraic Complexity Theory. The current best known bound is barely quadratic in the number of variables [Alon-Kumar-Volk, CCC 2017]. In this talk, we develop a framework for proving lower bounds for syntactic multilinear ABPs. We will show that rather than looking at the ABP, it might be beneficial to convert the ABP to a syntactic mulilinear formula with a super polynomial blow-up in the size and then exploit the structural limitations of resulting formula to obtain exponential lower bounds for special classes of multilinear ABPs as well as multilinear circuits. In particular, we prove exponential lower bounds for sum of Oblivious Read-Once ABPs - where every variable appears as edge labels in exactly one layer of the ABP. En route, we will also prove super-polynomial lower bounds for a special class of syntactic multilinear arithmetic circuits. |