ARC Colloquium: Gábor Braun

Title: Limiting linear programs through common information

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.

Event Details

Date/Time:

  • Monday, March 25, 2013
    1:30 pm
Location: Klaus 1116W

For More Information Contact