Algebraic Branching Programs (ABPs) whose computational power is encapsulated between that of arithmetic formulas and arithmetic circuits are standard models for computing polynomials. The absence of considerable progress on proving lower bounds for ABPs calls for further restrictions such as homogeneity and mutlilnearity. An ABP is said to be a syntactic multilinear ABP (smABP) if every variable appears as an edge label at most once on any path from source to sink. The best known size lower bound for smABPs is barely quadratic in the number of variables. Obtaining super-polynomial lower bounds for smABPs remains to be a challenging open problem in algebraic complexity theory.
By a simple divide and conquer approach, any smABP of polynomial size can be converted into an equivalent multilinear formula with a super-polynomial blow up in size. A crucial observation is that, although the above conversion of an smABP into a multilinear formula blows up the size, the resulting formula has far more structure than an arbitrary multilinear formula of super-polynomial size. In this talk, we try to identify and exploit the structural limitations of multilinear formulas thus obtained from smABPs. Using a finer analysis of these multilinear formulas, we outline a few approaches to prove super-polynomial lower bounds for smABPs.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
