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
