We study the approximability of predicates on k variables from a
domain [q], and give a new sufficient condition for such predicates
to be approximation resistant under the Unique Games Conjecture.
Specifically, we show that a predicate P is approximation resistant
if there exists a balanced pairwise independent distribution over
more >>>

We study constraint satisfaction problems on the domain \{-1,1\}, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form \mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n) for some positive integer weights w_1, \dots, w_n. Despite their simplicity, current techniques fall short of providing a classification ... more >>>

A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most O(1) constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... more >>>

We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain,
whenever k is larger than the domain size. This follows from our main result concerning predicates
over abelian groups. We show that a predicate is approximation resistant if it contains a subgroup that
is ... more >>>

Håstad established that any predicate P \subseteq \{0,1\}^m containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang ... more >>>

A boolean predicate f:\{0,1\}^k\to\{0,1\} is said to be {\em somewhat approximation resistant} if for some constant \tau > \frac{|f^{-1}(1)|}{2^k}, given a \tau-satisfiable instance of the MAX-k-CSP(f) problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let \tau(f) denote ... more >>>

For a predicate f:\{-1,1\}^k \mapsto \{0,1\} with \rho(f) = \frac{|f^{-1}(1)|}{2^k}, we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range [\rho(f)-\Omega(1), \rho(f)+\Omega(1)].

We present a characterization of ... more >>>

A predicate f:\{-1,1\}^k \mapsto \{0,1\} with \rho(f) = \frac{|f^{-1}(1)|}{2^k} 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 \rho(f)+\Omega(1) fraction of the constraints.

We present a complete characterization of approximation resistant predicates under the ... more >>>

A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to 1 with some probability \alpha achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), ... more >>>

An ordering constraint satisfaction problem (OCSP) is given by a positive integer k and a constraint predicate \Pi mapping permutations on \{1,\ldots,k\} to \{0,1\}. Given an instance of OCSP(\Pi) on n variables and m constraints, the goal is to find an ordering of the n variables that maximizes the number ... more >>>