Bringmann, Karl ;
Ikenmeyer, Christian ;
Zuiddam, Jeroen
On Algebraic Branching Programs of Small Width
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_ebar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_ebar 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 BenOr and Cleve showed that formula size is polynomially equivalent to width3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_ebar.
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.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs:2017:7521,
author = {Karl Bringmann and Christian Ikenmeyer and Jeroen Zuiddam},
title = {{On Algebraic Branching Programs of Small Width}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {20:120:31},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7521},
URN = {urn:nbn:de:0030drops75217},
doi = {10.4230/LIPIcs.CCC.2017.20},
annote = {Keywords: algebraic branching programs, algebraic complexity theory, border complexity, formula size, iterated matrix multiplication}
}
2017
Keywords: 

algebraic branching programs, algebraic complexity theory, border complexity, formula size, iterated matrix multiplication 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

2017 