DRAFT
Caltech Logo

Theory of Computing Seminar

Friday, May 20, 2016
12:00pm to 1:00pm
Add to Cal
Annenberg 314
Spectrahedral lifts of polytopes, sums of squares, and quantum information
James Lee, University of Washington,

Abstract:

Semi-definite programming is a powerful model of computation, but under widely accepted complexity-theoretic assumptions, it should not be able to solve NP-hard problems.  Until recently, it was unknown whether small SDPs could exactly capture, for instance, the traveling salesman polytopes.

I will present the known connections between semi-definite extension complexity, quantum information, low-degree sums of squares, and a notion of rank arising from factoring matrices through the PSD cone. 
 
In joint work with Raghavendra and Steurer, these tools are used to show that various polytopes underlying NP-complete problems do not admit small SDP formulations. 

 

For more information, please contact Thomas Vidick by email at vidick@cms.caltech.edu.