{"72819":{"#nid":"72819","#data":{"type":"event","title":"ARC Colloquium: Nikhil Bansal, IBM Research","body":[{"value":"\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EWe give a subexponential-time approximation algorithm for the Unique \u0026gt; Games \u0026gt; problem: Given a Unique Games instance with optimal value 1-epsilon \u0026gt; and alphabet size k, our algorithm finds in time exp(k*n^beta) a \u0026gt; solution of value 1-sqrt(epsilon\/beta^3). Here, beta\u0026gt;0 is a parameter \u0026gt; of the algorithm that can be chosen arbitrarily small. \u0026gt; \u0026gt; We also obtain subexponential algorithms with similar approximation \u0026gt; guarantees for Small-Set Expansion and Multi Cut. For Max Cut, \u0026gt; Sparsest Cut and Vertex Cover, our techniques lead to subexponential \u0026gt; algorithms with improved approximation guarantees on interesting subclasses of instances. \u0026gt; \u0026gt; Khot\u0027s Unique Games Conjecture (UGC) states that it is NP-hard to \u0026gt; achieve approximation guarantees such as ours for Unique Games. While \u0026gt; our results stop short of refuting the UGC, they do suggest that \u0026gt; Unique Games is significantly easier than NP-hard problems such as Max \u0026gt; 3-SAT, Label Cover and more, that are believed not to have \u0026gt; subexponential algorithms achieving a non-trivial approximation guarantee. \u0026gt; \u0026gt; The main component in our algorithms is a new kind of graph \u0026gt; decomposition that may have other applications: We show that every \u0026gt; graph with n vertices can be efficiently partitioned into disjoint \u0026gt; induced subgraphs, each with at most n^beta eigenvalues above 1-eta, \u0026gt; such that at most a \u0026gt; sqrt(epsilon\/beta^3) fraction of the edges of the graph does not \u0026gt; respect the partition. \u0026gt; \u0026gt; Joint work with Sanjeev Arora and Boaz Barak. \u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Constructive Algorithms for Discrepancy Minimization"}],"uid":"27263","created_gmt":"2011-11-16 12:02:32","changed_gmt":"2016-10-08 01:56:37","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2010-10-04T14:30:00-04:00","event_time_end":"2010-10-04T14:30:00-04:00","event_time_end_last":"2010-10-04T14:30:00-04:00","gmt_time_start":"2010-10-04 18:30:00","gmt_time_end":"2010-10-04 18:30:00","gmt_time_end_last":"2010-10-04 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"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":""}}}