event
ARC Colloquium: Pratik Worah - New York University
Primary tabs
Title: CSPs, Approximation Resistance, and Optimization HierarchiesAbstract:A 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). 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. One of the main problems in this area is to characterize which predicates are approximation resistant. 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. (Joint with S.Khot and M.Tulsiani).
Groups
Status
- Workflow Status: Published
- Created By: Elizabeth Ndongi
- Created: 02/14/2014
- Modified By: Fletcher Moore
- Modified: 04/13/2017
Categories
Keywords
Target Audience