ECCC-Report TR00-042https://eccc.weizmann.ac.il/report/2000/042Comments and Revisions published for TR00-042en-usFri, 17 Aug 2001 00:00:00 +0300
Revision 1
| The Non-Approximability of Non-Boolean Predicates Revision of: TR00-042 |
Lars Engebretsen
https://eccc.weizmann.ac.il/report/2000/042#revision1Constraint 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.
Fri, 17 Aug 2001 00:00:00 +0300https://eccc.weizmann.ac.il/report/2000/042#revision1
Paper TR00-042
| Lower Bounds for non-Boolean Constraint Satisfaction |
Lars Engebretsen
https://eccc.weizmann.ac.il/report/2000/042We 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.
Fri, 23 Jun 2000 15:50:29 +0300https://eccc.weizmann.ac.il/report/2000/042