[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

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/20150209/e6bda51e/attachment.htm