Extended formulations, non-negative factorizations and randomized communication protocols
Samuel Fiorini, Université Libre de Bruxelles

Extended formulations are a basic tool in combinatorial optimization: instead of optimizing over a polytope P directly, one may optimize over a higher-dimensional polyhedron Q that projects linearly to P. In some cases where P has many facets (say, exponentially many facets), it is possible to find an extended formulation Q that has a lot fewer facets (say, polynomially many), which makes the optimization easier. The motivation of this work is to understand when such a gain is possible.
In a seminal paper, Yannakakis (1991) proved (among other results) that the minimum number of facets in an extended formulation of a given polytope P is precisely the non-negative rank of the slack matrix of P, a certain matrix that one can naturally associate to P. He also observed that there is a connection between non-negative factorizations of binary matrices and deterministic communication protocols computing the corresponding binary function. He used this connection to obtain a sub-exponential size extended formulations for a certain important class of polytopes, namely, the stable set polytope of perfect graphs.
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 for perfect matching polytopes, which is another important class of polytopes in combinatorial optimization.

This is joint work with Michele Conforti, Yuri Faenza, Roland Grappe (Università di Padova) and Hans Raj Tiwary (Université Libre de Bruxelles)