Lower Bounds of Algebraic Branching Programs and Layerization

Abstract

In this paper we improve the lower bound of Chatterjee et al.\ (ECCC 2019) to an $\Omega (n^2)$ lower bound for unlayered Algebraic Branching Programs. We also study the impact layerization has on Algebraic Branching Programs. We exhibit a polynomial that has an unlayered ABP of size $O(n)$ but any layered ABP has size at least $\Omega (n\sqrt{n})$. We exhibit a similar dichotomy in the non-commutative setting where the unlayered ABP has size $O(n)$ and any layered ABP has size at least $\Omega (n\log n-{\log }^{2}n)$.

The current version has some serious gaps which I need to address before the results stand