<p>I landed on this page from a search about NAE-3SAT.</p>

<p>I am pretty sure that for the problem you are asking, it should be <em>NP-hard</em> 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 <em>tight</em> hardness result (matching what simply picking a random assignment would achieve), for <em>satisfiable</em> instances, and <em>no</em> need for the UGC.</p>

<p>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.</p>

<p>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.)</p>

<p>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.) </p>

<p>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.</p>

CC BY-SA 2.5
2010-12-13T18:47:20.707Z
Thanks for the great answer! I was unaware of the last paper you linked (yours with Engebretsen), and it will definitely help. I am still interested in the general case (and I've encountered a similar situation: it doesn't seem to be written anywhere!). Even something for the $\ell = 4$ and arbitrary $k$ case would very likely provide enough insight.
Daniel Apon
CC BY-SA 2.5
2010-12-13T16:17:42.223Z
2010-12-14T03:54:41.933Z
2010-12-14T03:54:41.933Z
Venkat Guruswami
<p>Prasad Raghavendra in his <a href="http://portal.acm.org/citation.cfm?id=1374376.1374414" rel="nofollow">STOC'08 Best Paper</a> 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. </p>

CC BY-SA 2.5
2010-11-21T23:44:51.660Z
Oh, good! I've spent some reading some other versions of Raghavendra's STOC paper, too. I should've made this connection! I don't know if the NAE values have been computed specifically either, but they'd definitely interest me!
Daniel Apon
CC BY-SA 2.5
2010-11-21T20:04:50.210Z
2010-11-21T20:04:50.210Z
Dana Moshkovitz
<p>I realized that what I claimed above is in fact known. </p>

<p>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).</p>

<p>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 <a href="http://eccc.hpi-web.de/report/2010/111/" rel="nofollow">http://eccc.hpi-web.de/report/2010/111/</a>). </p>

CC BY-SA 2.5
2011-02-02T22:23:10.603Z
That's quite beautiful. I'll probably end up using this in the very near future. Thank you!
Daniel Apon
CC BY-SA 2.5
2011-02-01T23:52:46.973Z
2011-02-07T19:17:06.920Z
2011-02-07T19:17:06.920Z
Venkat Guruswami
<p><strong>Background</strong>:</p>

<p>In Subhash Khot's original UGC paper (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.5651&amp;rep=rep1&amp;type=pdf" rel="nofollow">PDF</a>), 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$.</p>

<p>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,</p>

<p><strong>Question</strong>:</p>

<blockquote>
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$?
</blockquote>

<p>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)$.</p>

CC BY-SA 2.5
2010-10-12T22:13:08.020Z
Please a reference for case $k=3$?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-12T23:00:10.037Z
@turkistany, after looking at my question further, I decided to remove the sub-question (because I was asking just way too much all at once!). The paper I was originally referring to, though, was [this](http://portal.acm.org/citation.cfm?id=652168).
Daniel Apon
CC BY-SA 2.5
2010-10-13T06:42:35.843Z
If you do post a question about Bulatov's paper, note that there has been significant simplification of the approach over the last decade.  Several of the algorithms have been simplified and merged, see the recent LICS paper by Barto and Kozik for an overview.
András Salamon
CC BY-SA 2.5
2010-10-13T12:10:36.910Z
@Andras: I assume you mean [this](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5570979)? It's looks interesting; I'll definitely read it, thanks! In any case, I'll probably re-ask the previous sub-question as a new question soon, assuming I don't answer it for myself (plus, I'm short on time to ensure I state it properly at the moment).
Daniel Apon
CC BY-SA 2.5
2010-10-13T12:43:38.820Z
yes, that's the one.  The references therein provide a quick tour through the subsequent history.
András Salamon
<cc.complexity-theory><approximation-hardness><unique-games-conjecture><csp>
UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?
Daniel Apon
# UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?

(Asked by: username_0 on 2010-10-12)

**Background**:

In Subhash Khot's original UGC paper ([PDF](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.5651&rep=rep1&type=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)$.

**Tags:** cc.complexity-theory, approximation-hardness, unique-games-conjecture, csp
> **Comments:**
> **username_1**: Please a reference for case $k=3$?  
> **username_0**: @turkistany, after looking at my question further, I decided to remove the sub-question (because I was asking just way too much all at once!). The paper I was originally referring to, though, was [this](http://portal.acm.org/citation.cfm?id=652168).  
> **username_2**: If you do post a question about Bulatov's paper, note that there has been significant simplification of the approach over the last decade.  Several of the algorithms have been simplified and merged, see the recent LICS paper by Barto and Kozik for an overview.  
> **username_0**: @Andras: I assume you mean [this](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5570979)? It's looks interesting; I'll definitely read it, thanks! In any case, I'll probably re-ask the previous sub-question as a new question soon, assuming I don't answer it for myself (plus, I'm short on time to ensure I state it properly at the moment).  
> **username_2**: yes, that's the one.  The references therein provide a quick tour through the subsequent history.  

---

## 3 answers

### Answer by username_3 on 2011-02-01. Score: 9 | Accepted answer

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/>).

> **Comments:**
> **username_0**: That's quite beautiful. I'll probably end up using this in the very near future. Thank you!  

---

### Answer by username_3 on 2010-12-13. Score: 14

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.

> **Comments:**
> **username_0**: Thanks for the great answer! I was unaware of the last paper you linked (yours with Engebretsen), and it will definitely help. I am still interested in the general case (and I've encountered a similar situation: it doesn't seem to be written anywhere!). Even something for the $\ell = 4$ and arbitrary $k$ case would very likely provide enough insight.  

---

### Answer by username_4 on 2010-11-21. Score: 12

Prasad Raghavendra in his [STOC'08 Best Paper](http://portal.acm.org/citation.cfm?id=1374376.1374414) 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.

> **Comments:**
> **username_0**: Oh, good! I've spent some reading some other versions of Raghavendra's STOC paper, too. I should've made this connection! I don't know if the NAE values have been computed specifically either, but they'd definitely interest me!  

---

