Theory Seminar

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

Grant Schoenebeck

Friday, September 21, 2012
10:30am - 11:30am
3941 BBB

Add to Google Calendar

About the Event

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.

Additional Information

Sponsor(s): EECS

Open to: Public