Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR00-042 | 17th August 2001 00:00

The Non-Approximability of Non-Boolean Predicates Revision of: TR00-042


Revision #1
Authors: Lars Engebretsen
Accepted on: 17th August 2001 00:00
Downloads: 1396


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

Authors: Lars Engebretsen
Publication: 23rd June 2000 15:50
Downloads: 1696


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.

ISSN 1433-8092 | Imprint