[Colloquium] Theory Seminars at Computer Science
Donna Brooms
donna at cs.uchicago.edu
Fri Feb 13 08:17:09 CST 2015
~REMINDER~
THEORY SEMINAR
~Non-Standard Time~
Friday, February 13, 2014
Ryerson 255@ 10:30 a.m.
James R. Lee
University of Washington
homes.cs.washington.edu/~jrl
Title: “ Lower bounds on the size of semidefinite programming relaxations”
Abstract: We introduce a method for proving lower bounds on the size of SDP relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the affine image of the feasible region of any spectrahedron of dimension less than 2^{n^c} for some constant c > 0. A spectrahedron is the feasible region of an SDP: The intersection of the positive semidefinite cone and an affine subspace. This yields the first super-polynomial lower bound on the semidefinite extension complexity of any explicit family of polytopes.
Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a nonnegative matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares hierarchy. This can be alternately stated in the language of proof complexity and sum-of-squares representations of multivariate nonnegative real polynomials.
Our approach is to recast the problem in the language of quantum information theory. The main technical argument shows that high-entropy quantum states can be approximated by "low-degree" states with respect to low-degree test functionals.
This is based on joint work with Prasad Raghavendra and David Steurer.
Hosted by Prof. Alexander Razborov and Prof. Jian Ding from Statistics
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150213/1a7873f1/attachment.htm
More information about the Colloquium
mailing list