On Algebraic Branching Programs of Small Width
From MaRDI portal
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.
Recommendations
- On algebraic branching programs of small width
- On the power of algebraic branching programs of width two
- On the power of algebraic branching programs of width two
- Bounds for Width Two Branching Programs
- Stochastic Algorithms: Foundations and Applications
- Succinct algebraic branching programs characterizing non-uniform complexity classes
- A quadratic lower bound for algebraic branching programs
- scientific article; zbMATH DE number 36617
- scientific article; zbMATH DE number 706832
- scientific article; zbMATH DE number 7561749
Cited in
(19)- Blackbox identity testing for sum of special ROABPs and its border class
- A note on VNP-completeness and border complexity
- On the power of algebraic branching programs of width two
- On the power of algebraic branching programs of width two
- Succinct algebraic branching programs characterizing non-uniform complexity classes
- scientific article; zbMATH DE number 36617 (Why is no real title available?)
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Characterization and Lower Bounds for Branching Program Size Using Projective Dimension.
- scientific article; zbMATH DE number 7561749 (Why is no real title available?)
- On algebraic branching programs of small width
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- On the closures of monotone algebraic classes and variants of the determinant
- On the closures of monotone algebraic classes and variants of the determinant
- Young flattenings in the Schur module basis
- Geometric complexity theory for product-plus-power
- On the power of border width-2 ABPs over fields of characteristic 2
- Fixed-parameter debordering of Waring rank
- Homogeneous algebraic complexity theory and algebraic formulas
- Hitting sets for orbits of circuit classes and polynomial families
This page was built for publication: On Algebraic Branching Programs of Small Width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625653)
