Understanding the Limitations of Linear and Semidefinite Programming

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.