Bläser, Markus ;
Ikenmeyer, Christian ;
Mahajan, Meena ;
Pandey, Anurag ;
Saurabh, Nitin
Algebraic Branching Programs, Border Complexity, and Tangent Spaces
Abstract
Nisan showed in 1991 that the width of a smallest noncommutative single(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariskiclosed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width.
It was mentioned by Forbes that this result would probably break when going from single(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.
BibTeX  Entry
@InProceedings{blser_et_al:LIPIcs:2020:12573,
author = {Markus Bl{\"a}ser and Christian Ikenmeyer and Meena Mahajan and Anurag Pandey and Nitin Saurabh},
title = {{Algebraic Branching Programs, Border Complexity, and Tangent Spaces}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {21:121:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12573},
URN = {urn:nbn:de:0030drops125733},
doi = {10.4230/LIPIcs.CCC.2020.21},
annote = {Keywords: Algebraic Branching Programs, Border Complexity, Tangent Spaces, Lower Bounds, Geometric Complexity Theory, Flows, VQP, VNP}
}
17.07.2020
Keywords: 

Algebraic Branching Programs, Border Complexity, Tangent Spaces, Lower Bounds, Geometric Complexity Theory, Flows, VQP, VNP 
Seminar: 

35th Computational Complexity Conference (CCC 2020)

Issue date: 

2020 
Date of publication: 

17.07.2020 