Abstract:

Efficiently optimizing linear functions over a polytope by directly solving the linear program requires a compact representation of the polytope, e.g., as an affine image of a polytope with few facets. We present an information theoretic approach for proving limits of such extension: the common information shared by the vertices and facets.

This framework not only improves recent lower bounds on the CLIQUE polytope by Braverman and Moitra, but also provides a much simplified proof, and is stable under perturbations of the polytope.

This is an ongoing joint work with Sebastian Pokutta.