Theory of Computing Seminar

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.