ARC Colloquium: Gábor Braun

Primary tabs

Title: Limiting linear programs through common information


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.


  • Workflow Status:Published
  • Created By:Elizabeth Ndongi
  • Created:02/27/2013
  • Modified By:Fletcher Moore
  • Modified:10/07/2016


  • No keywords were submitted.