Tuesday, 16:15 - 16:40 h, Room: H 3004


Roland Grappe
Extended formulations, non-negative factorizations, and randomized communication protocols

Coauthors: Yuri Faenza, Samuel Fiorini, Tiwary Hans Raj


We show that the binary logarithm of the non-negative rank of a non-negative 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.


Talk 3 of the invited session Tue.3.H 3004
"Extended formulations in discrete optimization I" [...]
Cluster 2
"Combinatorial optimization" [...]


  Illinois Payday Loans should not be obtained by people who do not have the capacity to repay the lenders. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis Online is the one that definitely differs from all other products.