@inbook {IOPORT.06101778,
    author       = {Faenza, Yuri and Fiorini, Samuel and Grappe, Roland and Tiwary, Hans Raj},
    title        = {Extended formulations, nonnegative factorizations, and randomized communication protocols.},
    year         = {2012},
    booktitle    = {Combinatorial optimization. Second international symposium, ISCO 2012, Athens, Greece, April 19-21, 2012. Revised selected papers},
    isbn         = {978-3-642-32146-7},
    pages        = {129-140},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-32147-4_13},
    abstract     = {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.},
    identifier   = {06101778},
}