# Item

ITEM ACTIONSEXPORT

Released

Paper

#### On Algebraic Branching Programs of Small Width

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

arXiv:1702.05328.pdf

(Preprint), 443KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., Ikenmeyer, C., & Zuiddam, J. (2017). On Algebraic Branching Programs of Small Width. Retrieved from http://arxiv.org/abs/1702.05328.

Cite as: http://hdl.handle.net/11858/00-001M-0000-002D-89A4-8

##### Abstract

In 1979 Valiant showed that the complexity class VP_e of families with
polynomially bounded formula size is contained in the class VP_s of families
that have algebraic branching programs (ABPs) of polynomially bounded size.
Motivated by the problem of separating these classes we study the topological
closure VP_e-bar, i.e. the class of polynomials that can be approximated
arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a
strikingly simple complete polynomial (in characteristic different from 2)
whose recursive definition is similar to the Fibonacci numbers. Further
understanding this polynomial seems to be a promising route to new formula
lower bounds.
Our methods are rooted in the study of ABPs of small constant width. In 1992
Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3
ABP size. We extend their result (in characteristic different from 2) by
showing that approximate formula size is polynomially equivalent to approximate
width-2 ABP size. This is surprising because in 2011 Allender and Wang gave
explicit polynomials that cannot be computed by width-2 ABPs at all! The
details of our construction lead to the aforementioned characterization of
VP_e-bar.
As a natural continuation of this work we prove that the class VNP can be
described as the class of families that admit a hypercube summation of
polynomially bounded dimension over a product of polynomially many affine
linear forms. This gives the first separations of algebraic complexity classes
from their nondeterministic analogs.