- Series
- ACO Student Seminar
- Time
- Friday, November 16, 2012 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Sebastian Pokutta – Georgia Tech, ISyE – http://www.pokutta.com
- Organizer
- Cristóbal Guzmán
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. (joint work with Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf)