A Quadratic Lower Bound for Algebraic Branching Programs

An Algebraic Branching Program (ABP) is a layered graph where each edge is labeled by an affine linear form and the first and the last layer have one vertex each, called the “start” and the “end” vertex respectively. The polynomial computed by an ABP is equal to the sum of the weights of all paths from the start vertex to the end vertex in the ABP, where the weight of a path is equal to the product of the labels of all the edges on it. The size of an ABP is the number of vertices in it.

In this talk, we will see a proof of the following result. Any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices.

This improves upon the lower bound of $\Omega(n \log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results in [Kum19], which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial.

The talk is based on work done with Mrinal Kumar, Adrian She and Ben Lee Volk.