UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?

Question

Background:

In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary alphabet admits an assignment satisfying 1-$\epsilon$ of the constraints or whether there exist no assignments satisying $\frac{8}{9}+\epsilon$ of the constraints, for arbitrarily small $\epsilon > 0$.

I'm curious whether this result has been generalized for any combination of $\ell$-ary constraints for $\ell \ge 3$ and variable domains of size $k \ge 3$ where $\ell \ne k \ne 3$. That is,

Question:

Are there any known hardness of approximation results for the predicate $NAE(x_1, \dots, x_\ell)$ for $x_i \in GF(k)$ for $\ell, k \ge 3$ and $\ell \ne k \ne 3$?

I'm especially interested in the combination of values $\ell = k$; e.g., the predicate Not-all-equal($x_1, \dots, x_k$) for $x_1 \dots, x_k \in GF(k)$.

Answer 1

I realized that what I claimed above is in fact known.

For $\ell = 3$ and arbitrary $k \ge 3$, this is in Khot's FOCS 2002 paper "Hardness of coloring 3-colorable 3-uniform hypergraphs" (the paper actually talks about general $k$, though the title only talks about the 3-colorable case).

For $\ell \ge 4$ and $k \ge 2$, in fact a stronger hardness is known. Even if there is in fact an assignment of just two values to the variables that satisfies all NAE constraints (in other words the $\ell$-uniform hypergraph can be colored using 2 colors without any monochromatic hyperedge), it is still NP-hard to find an assignment from a domain size $k$ which satisfies at least $1-1/k^{\ell-1}+\epsilon$ NAE constraints (for arbitrary constant $\epsilon > 0$). This follows easily from the fact that the known inapproximability result for hypergraph 2-coloring gives a strong density statement in the soundness case. The formal statement appears in my SODA 2011 paper with Ali Sinop "The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number" (Lemma 2.3 in the SODA final version, and Lemma 2.8 in the older version available on ECCC http://eccc.hpi-web.de/report/2010/111/).

Answer 2

I landed on this page from a search about NAE-3SAT.

I am pretty sure that for the problem you are asking, it should be NP-hard to tell if the instance is satisfiable, or if at most $1-1/k^{\ell-1}+\epsilon$ fraction of constraints can be satisfied. That is, a tight hardness result (matching what simply picking a random assignment would achieve), for satisfiable instances, and no need for the UGC.

For $k=2$ and $\ell \ge 4$, this follows from Hastad's factor 7/8+epsilon inapproximability result for 4-set-splitting (which can then be reduced to k-set splitting for $k > 4$). If negations are okay, one can also use his tight hardness result for Max ($\ell-1$)-SAT.

For $k=\ell=3$, Khot proved this in a FOCS 2002 paper "Hardness of coloring 3-colorable 3-uniform hypergraphs." (That is, he removed the original UGC assumption.)

For $\ell=3$ and arbitrary $k\ge 3$, Engebretsen and I proved such a result in "Is constraint satisfaction over two variables always easy? Random Struct. Algorithms 25(2): 150-178 (2004)". However, I think our result required "folding" i.e., the constraints will actually be of the form NAE($x_i+a,x_j+b,x_k$) for some constants $a,b$. (This is the analog of allowing negations of Boolean variables.)

For the general case, I don't know if this has been written down anywhere. But if you really need it, I can probably find something or check the claim.

Answer 3

Prasad Raghavendra in his STOC'08 Best Paper proved, assuming the Unique Games Conjecture, that a simple semidefinite programming algorithm gives the best approximation for any constraint satisfaction problem (including NAE) with constraints on constant number of variables each and with constant alphabet. To actually know what is the hardness factor for NAE, you need to understand how well the simple algorithm does for it, i.e., prove an integrality gap for the program. I don't know whether someone already did that for NAE in its full generality, or not.