Theory of Computing Seminar
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.
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.
Event Series
Theory of Computing Seminar Series