Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SÉBASTIEN TAVENAS:
All reports by Author Sébastien Tavenas:

TR19-100 | 31st July 2019
Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas

Nonnegative rank measures and monotone algebraic branching programs

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 ... more >>>




ISSN 1433-8092 | Imprint