Lower Bounds of Algebraic Branching Programs and Layerization

In this paper we improve the lower bound of Chatterjee et al.\ (ECCC 2019) to an $Ω(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 $Ω(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 $Ω(n\log n -\log^2 n)$.

No reviews yet.

No comments yet.