*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
