{"187591":{"#nid":"187591","#data":{"type":"event","title":"ARC Colloquium, Madhur Tulsiani, Toyota Technological Institute at Chicago","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E The Complexity of Somewhat Approximation Resistant Predicates\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EFor a Boolean predicate f on k variables, let \\rho(f) be the probability that a constraint of the form f(x_1,...,x_k) is satisfied by a random assignment. A predicate f is called \u0022somewhat approximation resistant\u0022 if for some constant \\tau \u0026gt; \\rho(f), given a \\tau-satisfiable instance of the Max-k-CSP(f) problem, it is NP-hard to find an assignment that strictly beats the naive algorithm that outputs a uniformly random assignment.\u003C\/p\u003E\u003Cp\u003ELet \\tau(f) denote the supremum over all \\tau for which the above holds. It is known that a predicate is somewhat approximation resistant precisely when its Fourier degree is at least 3. For such predicates, we give a characterization of the \u0022hardness gap\u0022 (\\tau(f) -\\rho(f)) up to a factor of O(k^5). We also give a similar characterization of the integrality gap for the natural SDP relaxation of Max-k-CSP after \\Omega(n) rounds of the Lasserre hierarchy.\u003C\/p\u003E\u003Cp\u003EJoint work with Subhash Khot and Pratik Worah.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-01-29 09:27:57","changed_gmt":"2016-10-08 02:02:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-03-11T14:30:00-04:00","event_time_end":"2013-03-11T15:30:00-04:00","event_time_end_last":"2013-03-11T15:30:00-04:00","gmt_time_start":"2013-03-11 18:30:00","gmt_time_end":"2013-03-11 19:30:00","gmt_time_end_last":"2013-03-11 19:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"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\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}