Exponential Lower Bounds for Polytopes in Combinatorial Optimization

SHARE:

Event Speaker: 

Ronald de Wolf, CWI

Event Location: 

32-124

Card Description: 

We solve a 20-year old problem posed by Yannakakis and prove that 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.

Event Date/Time: 

Thursday, September 6, 2012 - 4:15pm

Research Area: 

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Speaker: Ronald de Wolf, CWI
Date: Thursday, September 6 2012
Time: 4:15PM to 5:15PM
Refreshments: 3:45PM
Location: 32-124
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu

Relevant URL: Special Date - Joint with ORC

We solve a 20-year old problem posed by Yannakakis and prove that 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. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs. Joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, at STOC'12 (shared Best Paper Award).

See other events that are part of Theory Colloquium 2012/2013

See other events happening in September 2012