Projections to the TSP Polytope

Michael Ben Or told me about the following great paper Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf. The paper solves an old conjecture of Yannakakis about projections of polytopes.

From the abstract: “We solve a 20-year old problem posed by M. 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 maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.”

There are many interesting aspects to this story. The starting point was a series of papers in the 80s trying to prove that P=NP by solving TSP using linear programming. The idea was to present the TSP polytope as a projection of a larger dimensional polytope described by  polynomially many linear inequalities, and solve the LP problem on that larger polytope.  Yannakakis proved that such attempts are doomed to fail, when the larger LP problem keep the symmetry of the original TSP polytope.

Yannakakis asked if the symmetry condition can be removed and this is what the new paper shows. This is a very interesting result also from the point of view of convex polytope theory.

Another exciting aspect of the paper is the use of methods from quantum communication complexity.

Update: See this post over GLL for discussion and a description of a follow up paper.


About these ads

One thought on “Projections to the TSP Polytope

  1. It is a nice paper with many cool connections. I was a bit disappointed that the quantum/SDP stuff is not actually used in any way to solve Yannakakis’ problem, what they say in the abstract seems to be over-selling things. They do link quantum stuff to classical SDP stuff which is great. But the proof is nice and it is great to resolve the old problem. The paper is also very readable and you can skip all the SDP and quantum stuff if you just want to see what they do with regards to Yannakakis’ problem.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s