skip to main content
Caltech
Fires burning in Greater Los Angeles area have had significant impact on the Caltech's community and surrounding areas. For information and resources for members of the Caltech community, go to https://www.caltech.edu/fire.

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.