BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Theory Seminar: Lower bounds on the size of semidefinite programmi
 ng relaxations
DTSTART:20141216T150000
DTEND:20141216T160000
DTSTAMP:20260428T004614Z
UID:0f4414ce333551fa2ba006c16d3bb6dd12bd5cfcab7e3ff122d6affa
CATEGORIES:Conferences - Seminars
DESCRIPTION:David Steurer\, Cornell University\nWe introduce a method for 
 proving lower bounds on the efficacy of semidefinite programming (SDP) rel
 axations for combinatorial problems. In particular\, we show that the cut\
 , TSP\, and stable set polytopes on n-vertex graphs are not the linear ima
 ge of the feasible region of any SDP (i.e.\, any spectrahedron) of dimensi
 on less than 2nδ\, for some constant δ>0. This result yields the first s
 uper-polynomial lower bounds on the semidefinite extension complexity of a
 ny explicit family of polytopes.\nOur results follow from a general techni
 que 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 ma
 ximum constraint satisfaction problems\, we prove that SDPs of polynomial-
 size are equivalent in power to those arising from degree-O(1) sum-of-squa
 res relaxations. This result implies\, for instance\, that no family of po
 lynomial-size SDP relaxations can achieve better than a 7/8-approximation 
 for MAX 3 SAT.\nJoint work with James R. Lee\, Prasad Raghavendra.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR