jQuery('#ajaxmodal .modal-body-content').html('
\nRecorded\n14 June 2012\nin Lausanne, Vaud, Switzerland\n<\/p>\n
\nEvent:<\/b>\nSuRI<\/a>\n- I&C - Summer Research Institute\n<\/p>\n We survey recent results about semidefinite programming (SDP) hierarchies in the context of the Unique Games Conjecture. This conjecture has emerged as a unifying approach towards settling many central open problems in the theory of approximation algorithms. It posits the hardness of a certain constraint satisfaction problem, called Unique Games.<\/p>\n\n We explain recent approximation algorithms based on SDP hierarchies that approximate this problem in subexponential time. This result relies on a connection between the spectrum of graphs and the expansion of small sets. Recent constructions show that algorithms based on this connection cannot run much faster than in subexponential time. Finally, we discuss evidence how stronger SDP hierarchies based on sum-of-squares proofs might be able to go beyond this limitation.<\/p>\n\n<\/div>\n Watched 1325 times.<\/p>\n<\/i> Watch<\/a>\n<\/div>\n<\/div>\n<\/div>\n');
jQuery('#ajaxmodal .modal-title').html("Talk Details");
jQuery('#ajaxmodal').modal({keyboard: true, show: true});
Abstract<\/h4>\n