16
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please a reference for case $k=3$? $\endgroup$ – Mohammad Al-Turkistany Oct 12 '10 at 22:13
  • $\begingroup$ @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. $\endgroup$ – Daniel Apon Oct 12 '10 at 23:00
  • 2
    $\begingroup$ 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. $\endgroup$ – András Salamon Oct 13 '10 at 6:42
  • 1
    $\begingroup$ @Andras: I assume you mean this? 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). $\endgroup$ – Daniel Apon Oct 13 '10 at 12:10
  • $\begingroup$ yes, that's the one. The references therein provide a quick tour through the subsequent history. $\endgroup$ – András Salamon Oct 13 '10 at 12:43
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That's quite beautiful. I'll probably end up using this in the very near future. Thank you! $\endgroup$ – Daniel Apon Feb 2 '11 at 22:23
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel Apon Dec 13 '10 at 18:47
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Daniel Apon Nov 21 '10 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.