Abstract:
We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We extend the techniques of Samorodnitsky and Trevisan to obtain a UGC hardness result when $q$ is a prime. More precisely, assuming the Unique Games Conjecture, we show that it is NP-hard to approximate the problem to a ratio greater than $q^2k/q^k$. Independent of this work, Austrin and Mossel obtain a more general UGC hardness result using entirely different techniques. We also obtain an approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Except for constant factors depending on $q$, the algorithm and the UGC hardness result have the same dependence on the arity $k$. It has been pointed out to us by Makarychev and Makarychev that a similar approximation ratio can be obtained by reducing the non-boolean case to a boolean CSP, and appealing to the CMM algorithm. As a subroutine, we design a constant factor (depending on $q$) approximation algorithm for the problem of maximizing a semidefinite quadratic form, where the variables are constrained to take values on the corners of the $q$-dimensional simplex. This result generalizes an algorithm of Nesterov for maximizing semidefinite quadratic forms where the variables take $\{-1,1\}$ values.

Abstract:
We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to obtain a UGC hardness result when $q$ is a prime. More precisely, assuming the Unique Games Conjecture, we show that it is NP-hard to approximate the problem to a ratio greater than $q^2k/q^k$. Except for constant factors depending on $q$, the algorithm and the UGC hardness result have the same dependence on the arity $k$.