Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] theory seminar thursday with Prasad Raghavendra on SDP lower bounds

Gregory Valiant gvaliant at
Wed Oct 28 12:11:01 PDT 2015

Hi Everyone,
We are delighted to have Prasad Raghavendra coming down from Berkeley
to give tomorrow's theory seminar.  (Talk starts @4:15, refreshments
starting around 4pm in Gates 463a.)

Title:  Lower bounds on the size of semidefinite programming relaxations

We introduce a method for proving lower bounds on the efficacy of
semidefinite programming (SDP) relaxations for combinatorial problems.
In particular, we show that the cut, TSP, and stable set polytopes on
n-vertex graphs are not the linear image of the feasible region of any
SDP (i.e., any spectrahedron) of dimension less than 2nc, for some
constant c>0. This result yields the first super-polynomial lower
bounds 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 matrix. To this end, we
establish a close connection between arbitrary SDPs and those arising
from the sum-of-squares SDP hierarchy. For approximating maximum
constraint satisfaction problems, we prove that SDPs of
polynomial-size are equivalent in power to those arising from
degree-O(1) sum-of-squares relaxations. This result implies, for
instance, that no family of polynomial-size SDP relaxations can
achieve better than a 7/8-approximation for MAX-3-SAT.

This is joint work with James Lee (U. Washington) & David Steurer
(Cornell Univ).

More information about the theory-seminar mailing list