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.


Editor(s):
Mahjoub, A. Ridha
Markakis, Vangelis
Milis, Ioannis
Paschos, Vangelis Th.
Published in:
Combinatorial Optimization, 7422, 129-140
Presented at:
2nd International Symposium on Combinatorial Optimization (ISCO 2012)
Year:
2012
Publisher:
Berlin, Heidelberg, Springer Berlin Heidelberg
Keywords:
Laboratories:




 Record created 2012-10-25, last modified 2018-03-17

Preprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)