TY - GEN
T1 - Nonnegative rank measures and monotone algebraic branching programs
AU - Fournier, Hervé
AU - Malod, Guillaume
AU - Szusterman, Maud
AU - Tavenas, Sébastien
N1 - Publisher Copyright:
© Hervé Fournier, Guillaume Malod, Maud Szusterman, and Sébastien Tavenas; licensed under Creative Commons License CC-BY.
PY - 2019/12/1
Y1 - 2019/12/1
N2 - 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.
AB - 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.
KW - Elementary symmetric polynomials
KW - Lower bounds
UR - https://www.scopus.com/pages/publications/85077465154
U2 - 10.4230/LIPIcs.FSTTCS.2019.15
DO - 10.4230/LIPIcs.FSTTCS.2019.15
M3 - Conference contribution
AN - SCOPUS:85077465154
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019
A2 - Chattopadhyay, Arkadev
A2 - Gastin, Paul
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019
Y2 - 11 December 2019 through 13 December 2019
ER -