### DIMACS Theoretical Computer Science Seminar

Title: Understanding the Limitations of Linear and Semidefinite Programming

Speaker: ** Grant Schoenebeck**, Princeton University

Date: Wednesday, March 23, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Linear and Semidefinite programs provide the best approximation
algorithms for many NP-hard combinatorial optimization problems. This talk
will introduce recent techniques to give unconditional lower bounds for
algorithms based on Linear and Semidefinite programs (LPs and SDPs,
respectively). In particular, I will define and give background about LP and
SDP hierarchies, which include a large class of SDPs and LPs including the
most famous SDP algorithms (which occur very low in the hierarchy). I will
then sketch two lower bounds for these hierarchies. The first result shows
that a large class of linear programs (generated by the Lovasz-Schrijver
hierarchy) requires exponential time to approximate Vertex Cover to better
than a factor of 2-epsilon. The second result shows that a large class of
semidefinite programs (generated by the Lasserre hierarchy) requires
exponential time to refute a random 3-XOR instance (even though such an
instance is very far from satisfiable). As a corollary, the same class
requires exponential time to
approximate Vertex Cover to better than a factor of 7/6-epsilon. This result
is the first construction of a Lasserre integrality gap, and simplifies,
strengthens, and helps to explain several previous results.