BEGIN:VCALENDAR
PRODID:-//Mercury//HGEvent//EN
VERSION:2.0
METHOD:PUBLISH
BEGIN:VEVENT
STATUS:CONFIRMED
LAST-MODIFIED:20140902T201512
PRIORITY:0
CLASS:PUBLIC
UID:ATEvent-eed436ece7e23bbcfe0d4623c4969225
SUMMARY:ARC Colloquium: Pratik Worah - New York University
DESCRIPTION:Title: CSPs\, Approximation Resistance\, and Optimization Hierarchies\nAbstract:\nA 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).\n 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.\n One of the main problems in this area is to characterize which predicates are approximation resistant.\n 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.\n (Joint with S.Khot and M.Tulsiani).\n
DTSTART:20140226T133000
DTEND:20140226T133000
CREATED:20140219T171513
DTSTAMP:20140219T171513
SEQUENCE:0
LOCATION:
END:VEVENT
END:VCALENDAR