{"72829":{"#nid":"72829","#data":{"type":"event","title":"ARC Colloquium: David Steurer, Microsoft","body":[{"value":"\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EWe give a subexponential-time approximation algorithm for the Unique Games problem: Given a Unique Games instance with optimal value 1-epsilon and alphabet size k, our algorithm finds in time exp(k*n^beta) a solution of value 1-sqrt(epsilon\/beta^3). Here, beta\u0026gt;0 is a parameter of the algorithm that can be chosen arbitrarily small.\u003C\/p\u003E\u003Cp\u003EWe also obtain subexponential algorithms with similar approximation guarantees for Small-Set Expansion and Multi Cut.\u0026nbsp; For Max Cut, Sparsest Cut and Vertex Cover, our techniques lead to subexponential algorithms with improved approximation guarantees on interesting subclasses of instances.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;Khot\u0027s Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for Unique Games.\u0026nbsp; While our results stop short of refuting the UGC, they do suggest that Unique Games is significantly easier than NP-hard problems such as Max 3-SAT, Label Cover and more, that are believed not to have subexponential algorithms achieving a non-trivial approximation guarantee.\u003C\/p\u003E\u003Cp\u003EThe main component in our algorithms is a new kind of graph decomposition that may have other applications: We show that every graph with n vertices can be efficiently partitioned into disjoint induced subgraphs, each with at most n^beta eigenvalues above 1-eta, such that at most a sqrt(epsilon\/beta^3) fraction of the edges of the graph does not respect the partition.\u003C\/p\u003E\u003Cp\u003EJoint work with Sanjeev Arora and Boaz Barak.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Subexponential Algorithms for Unique Games and Related Problems"}],"uid":"27263","created_gmt":"2011-11-16 13:04:23","changed_gmt":"2016-10-08 01:56:41","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2010-11-29T12:30:00-05:00","event_time_end":"2010-11-29T12:30:00-05:00","event_time_end_last":"2010-11-29T12:30:00-05:00","gmt_time_start":"2010-11-29 17:30:00","gmt_time_end":"2010-11-29 17:30:00","gmt_time_end_last":"2010-11-29 17:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}