Chicago Journal of Theoretical Computer Science

Volume 2016

Article 2

Published by the Department of Computer Science, The University of Chicago.

Nonnegative Rank vs. Binary Rank

Thomas Watson
Department of Computer Science
University of Toronto
Toronto, ON, Canada
thomas DOT watson AT cs DOT toronto DOT edu

February 22, 2016


Motivated by (and using tools from) communication complexity, we investigate the relationship between the following two ranks of a $0$-$1$ matrix: its nonnegative rank and its binary rank (the $\log$ of the latter being the unambiguous nondeterministic communication complexity). We prove that for partial $0$-$1$ matrices, there can be an exponential separation. For total $0$-$1$ matrices, we show that if the nonnegative rank is at most $3$ then the two ranks are equal, and we show a separation by exhibiting a matrix with nonnegative rank $4$ and binary rank $5$, as well as a family of matrices for which the binary rank is $4/3$ times the nonnegative rank.

Submitted February 3, 2014, revised August 15, 2015, and on February 17, 2016, published February 22, 2016.

DOI: 10.4086/cjtcs.2016.002

[] Volume 2016, Article 1
[back] Volume 2016 [back] Published articles
[CJCTS home]