期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2016
卷号：2016
页码：1-13
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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
关键词：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.
