{"276131":{"#nid":"276131","#data":{"type":"event","title":"ARC Colloquium: Pratik Worah - New York University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle\u003C\/strong\u003E: CSPs, Approximation Resistance, and Optimization Hierarchies\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003C\/p\u003E\u003Cp\u003EA k-ary boolean predicate f, naturally implies a canonical constraint satisfaction problem (CSP(f)). Let MAX k-CSP(f) denote the problem of finding the maximum fraction of simultaneously satisfiable constraints in any given instance of CSP(f). A trivial randomized algorithm achieves an approximation factor proportional to f^{-1}(1).\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;On the other hand, it is known, for some f, that an efficient algorithm can not perform strictly better than the trivial algorithm - such f are known as approximation resistant.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;One of the main problems in this area is to characterize which predicates are approximation resistant.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;In this talk, I will survey known bounds for CSPs and their connections with LP and SDP hierarchies. Finally, I will give an overview of my recent research in this area, which gives a characterization of approximation resistance.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;(Joint with S.Khot and M.Tulsiani).\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"CSPs, Approximation Resistance, and Optimization Hierarchies"}],"uid":"27263","created_gmt":"2014-02-14 16:01:41","changed_gmt":"2017-04-13 21:23:11","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-02-26T12:30:00-05:00","event_time_end":"2014-02-26T12:30:00-05:00","event_time_end_last":"2014-02-26T12:30:00-05:00","gmt_time_start":"2014-02-26 17:30:00","gmt_time_end":"2014-02-26 17:30:00","gmt_time_end_last":"2014-02-26 17: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":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"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":""}}}