Extended formulations, nonnegative factorizations, and randomized communication protocols (Q745681)

An extended formulation of a polytope \(P\) is a linear description of \(P\) in an extended space. \(P\) can be considered as the projection of the polyhedron of the extension. Extended formulations are of interest because every optimization problem on \(P\) can also be defined over an extension of \(P\) and the number of constraints might be substantially smaller. \(P\) can have many facets but optimizing over \(P\) can be done efficiently if the separation problem for \(P\) can be solved efficiently. The advantage of extensions can be that an increase in the dimension might lead to a substantial reduction in the number of facets. Yannakakis' factorization theorem connects the extension of a polytope to a nonnegative factorization of a matrix associated to \(P\) and vice versa. The authors strengthen the connection between the nonnegative rank of matrices and communication protocols and show that allowing randomization in the protocol can be important for obtaining small extended formulations. They prove that for the spanning tree and perfect matching polytopes a small variance in the protocol leads to a large size of the extended formulation.