Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.15
URN: urn:nbn:de:0030-drops-115774
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11577/
Fournier, Hervé ; Malod, Guillaume ; Szusterman, Maud ; Tavenas, Sébastien
Nonnegative Rank Measures and Monotone Algebraic Branching Programs
| pdf-format: |
|
Abstract
Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove a rather tight lower bound for the computation of elementary symmetric polynomials by algebraic branching programs in the monotone setting or, equivalently, in the homogeneous syntactically multilinear setting.
BibTeX - Entry
@InProceedings{fournier_et_al:LIPIcs:2019:11577,
author = {Herv{\'e} Fournier and Guillaume Malod and Maud Szusterman and S{\'e}bastien Tavenas},
title = {{Nonnegative Rank Measures and Monotone Algebraic Branching Programs}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {15:1--15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-131-3},
ISSN = {1868-8969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11577},
URN = {urn:nbn:de:0030-drops-115774},
doi = {10.4230/LIPIcs.FSTTCS.2019.15},
annote = {Keywords: Elementary symmetric polynomials, lower bounds}
}
| Keywords: | Elementary symmetric polynomials, lower bounds | |
| Seminar: | 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 04.12.2019 |
