Name
Abstract | ||
|---|---|---|
Inspired by Nisanu0027s 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.FSTTCS.2019.15 | Electronic Colloquium on Computational Complexity (ECCC) |
Field | DocType | Volume |
Noncommutative geometry,Discrete mathematics,Combinatorics,Algebraic number,Computer science,Upper and lower bounds,Elementary symmetric polynomial,Nonnegative rank,Multilinear map,Monotone polygon,Computation | Conference | 26 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hervé Fournier | 1 | 0 | 0.34 |
| Guillaume Malod | 2 | 54 | 4.53 |
| Maud Szusterman | 3 | 0 | 0.34 |
| Sébastien Tavenas | 4 | 0 | 0.34 |