Constraint satisfaction programs where each constraint
depends on a constant number of variables have the following property:
The randomized algorithm that guesses an assignment uniformly at
random satisfies an expected constant fraction of the constraints. By
combining constructions from interactive proof systems with harmonic
analysis over finite groups, Håstad showed that for several
constraint satisfaction programs this naive algorithm is essentially
the best possible unless P = NP. While most of the predicates
analyzed by Håstad depend on a small number of variables,
Samorodnitsky and Trevisan recently extended Håstad's result to
predicates depending on an arbitrarily large, but still constant,
number of Boolean variables.

We combine ideas from these two constructions and prove that there
exists a large class of predicates on finite non-Boolean domains
such that for predicates in the class, the naive randomized
algorithm that guesses a solution uniformly is essentially the best
possible unless P = NP. As a corollary, we show that the k-CSP
problem over domains with size D cannot be approximated within
D^{k-O(sqrt{k})} - epsilon, for any constant epsilon > 0,
unless P = NP. This lower bound matches well with the best known
upper bound, D^{k-1}, of Serna, Trevisan and Xhafa.

We show that the k-CSP problem over a finite Abelian group G
cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for
any constant epsilon>0, unless P=NP. This lower bound matches
well with the best known upper bound, |G|^{k-1}, of Serna,
Trevisan and Xhafa. The proof uses a combination of PCP
techniques---most notably a recent recycling construction of
Samorodnitsky and Trevisan---with Fourier analysis of functions
from a finite Abelian group to the complex numbers.