*********************************
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: Extended formulations and complexity of polytopes
Abstract:
In the first part we will analyze extended formulations of polytopes and we solve a 20-year old problem posed by Yannakakis: there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope.
In view of the aforementioned lower bounds we then turn our attention, in the second part, to approximate extended formulations which approximately project to the desired polytope. We develop a framework for proving approximation limits of polynomial-size linear programs. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^{1/2−ε})-approximations for CLIQUE require linear programs of size 2^{n^Ω(ε)}. Moreover, we establish a similar result for approximations of semidefinite programs by linear programs.
This is joint work with G ́abor Braun, Samuel Fiorini, Serge Massar, David Steurer, Hans Raj Tiwary, and Ronald de Wolf
