Tuesday, May 19, 2015 - 4:15pm to 5:15pm

Refreshments:

Light Refreshments at 4pm

Location:

G449 (Patil/Kiva)

Speaker:

David Steurer, Cornell University

Seminar group:

Abstract:

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 2* ^{nδ }*, for some constant

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.

Based on joint work with James R. Lee and Prasad Raghavendra.