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.

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$.