A predicate f:?11k01 with (f)=2kf?1(1) is called {it approximation resistant} if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment that satisfies at least (f)+(1) fraction of the constraints. We present a complete characterization of approximation resistant predicates under the Unique Games Conjecture. We also present characterizations in the {it mixed} linear and semi-definite programming hierarchy and the Sherali-Adams linear programming hierarchy. In the former case, the characterization coincides with the one based on UGC. Each of the two characterizations is in terms of existence of a probability measure with certain symmetry properties on a natural convex polytope associated with the predicate.This is a revised version of out previous paper which gave a characterization for a modified notion called "Strong Approximation Resistance".
展开▼
