id: 06101778
dt: a
an: 06101778
au: Faenza, Yuri; Fiorini, Samuel; Grappe, Roland; Tiwary, Hans Raj
ti: Extended formulations, nonnegative factorizations, and randomized
    communication protocols.
so: 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).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: extended formulations; nonnegative rank; communication protocols
ci: 
li: doi:10.1007/978-3-642-32147-4_13
ab: 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.
rv: