__
Revision #1 to TR00-042 | 17th August 2001 00:00
__
#### The Non-Approximability of Non-Boolean Predicates Revision of: TR00-042

**Abstract:**
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.

__
TR00-042 | 21st June 2000 00:00
__

#### Lower Bounds for non-Boolean Constraint Satisfaction

**Abstract:**
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.