Extended formulations, non-negative factorizations and randomized communication protocols

Yuri Faenza, Samuel Fiorini, Roland Grappe +1

An extended formulation of a polyhedron $P$ is a linear description of a polyhedron $Q$ together with a linear map $\pi$ such that $\pi (Q)=P$. These objects are of fundamental importan…