Le séminaire AOC recevra le 28 avril Roland Grappe (post-doc, Padoue)

Attention, cette séance aura lieu le jeudi à midi au lieu de l’horaire habituel.

An extended formulation of a polyhedron P is a polyhedron in a higher dimensional space whose projection is P. In a seminal paper, Yannakakis (1991) proved that the minimum number of facets in an extended formulation of a given polytope is the non-negative rank of its slack matrix.

We show that the non-negative rank of a non-negative matrix is (up to small constants) determined by the minimum complexity of a randomized communication protocol computing the matrix on average.

We then use this connection to prove novel conditional lower bounds on the sizes of extended formulations, in particular, for perfect matching polytopes.

This is joint work with Michele Conforti, Yuri Faenza, Samuel Fiorini and Hans Raj Tiwary.