Dana Moshkovitz: Candidate Lasserre Integrality Gap for Unique Games
Friday, November 14, 2014 - 12:45pm to 3:45pm
Refreshments:
Pizza at 12:30pm
Location:
MIT (Stata Center, Hewlett room, 32-G882)
Speaker:
Dana Moshkovitz
Biography:
NUT
Seminar group:
The Unique Games Conjecture of Khot is the basis of remarkable inapproximability results. In recent years, researchers have explored possible algorithms for refuting it based on the Lasserre (aka Sum of Squares) hierarchy of semidefinite programs.
In the talk we'll show a candidate hard instance for algorithms based on the Lasserre hierarchy.
Joint work with Subhash Khot.