Motivated by the pervasiveness of strong inapproximability results for MaxCSPs, we introduce a relaxed version of the MaxCSP. In this relaxed version, loosely speaking, the algorithm is allowed to replace the constraints of an instance by some other constraints, and then only needs to satisfy as many of the new constraints as possible. For instance, given a Max 3-Lin instance, the algorithm would be allowed to change all the constraints to 3-Sat constraints.

We consider the following (very weak) notion of such an algorithm being good: given that the original MaxCSP instance is almost satisfiable, the algorithm succeeds if it beats a random assignment on the new instance with the constraints replaced. We say that a MaxCSP is useful if there is a good algorithm for it.

Under the Unique Games Conjecture, we can give a complete and simple characterization of useful MaxCSPs defined by a predicate: such a MaxCSP is useful if and only if there is a pairwise independent distribution supported on its satisfying assignments.

(Joint work with Johan Håstad)