Unconditional hardness results for semi-definite programs: integrality gaps for the Lasserre hierarchy

Semidefinite programs provide the best approximation algorithms for many NP-hard combinatorial optimization problems. Recently, techniques were developed to give unconditional lower bounds for algorithms based on SDPs. I will define and give background about semidefinite program (and linear program) hierarchies, which include a large class of SDPs (and LPs) including all the most famous SDP algorithms (which actually occur very low in the hierarchy). I will then show a lower bound that implies no SDP in this large class can refute a random 3-XOR instance (even though such a instances is very far from satisfiable). Finally, I will discuss some corollaries, implications, and open problems.