*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: CSPs, Approximation Resistance, and Optimization Hierarchies
Abstract:
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).
