A Quadratic Lower Bound for Algebraic Branching Programs and Formulas

Prerona Chatterjee, Mrinal Kumar, Adrian She +1

We show that 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 $Ω(n\log n)…