06101778

a

06101778 Faenza, Yuri Fiorini, Samuel Grappe, Roland Tiwary, Hans Raj Extended formulations, nonnegative factorizations, and randomized communication protocols. Mahjoub, A. Ridha (ed.) et al., Combinatorial optimization. Second international symposium, ISCO 2012, Athens, Greece, April 19-21, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-32146-7/pbk). Lecture Notes in Computer Science 7422, 129-140 (2012). 2012 Berlin: Springer EN extended formulations nonnegative rank communication protocols

doi:10.1007/978-3-642-32147-4_13

Summary: 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.