Infoscience

Conference paper

Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

We show that the binary logarithm of the nonnegative rank of a nonnegative matrix is, up to small constants, equal to the minimum complexity of a randomized communication protocol computing the matrix in expectation. We use this connection to prove new conditional lower bounds on the sizes of extended formulations, in particular, for perfect matching polytopes.

Related material