Theory of Computing Seminar

Friday May 20, 2016 12:00 PM

Spectrahedral lifts of polytopes, sums of squares, and quantum information

Speaker: James Lee, University of Washington
Location: Annenberg 314

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. 

 

Series Theory of Computing Seminar Series

Contact: Thomas Vidick vidick@cms.caltech.edu