<p>Here is a summary of what is known about approximability of $k$-CSP over a domain of size $q$:</p>

<ul>
<li>The best known approximation algorithms for the problem give an $\Omega(q \max(k, \log q)/q^k)$ approximation [MM14 and MNT16].</li>
<li>For $k = \Omega(q)$, there is a matching hardness of $O(kq/q^k)$ by Håstad (UGC-hardness) and Chan (NP-hardness) [Chan13].</li>
<li>For $k$ between $c \log q  /  \log \log q$ and $q$, the best known NP-hardness result is $O(q^2/q^k)$ (follows from [Chan13]).</li>
<li>For $2 &lt; k &lt; c \log q  /  \log \log q$, the best known UGC-hardness is $2^{O(k \log k)} q \, (\log q)^{k/2}/q^k$ by Manurangsi et al. [MNT16].</li>
<li>For $k=2$, the best NP-hardness is $O(\log q/\sqrt{q})$ by Chan [Chan13], the best UGC-hardness is $O(\log q/q^k)$ by Khot et al. [KKMO07]</li>
</ul>

<p>[Chan13] Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings of the Symposium on Theory of Computing, pages 447–456, 2013.</p>

<p>[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproxima bility results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007.</p>

<p>[MM14] Konstantin Makarychev and Yury Makarychev. Approximation algorithm for non-Boolean Max $k$-CSP. Theory of Computing, 10(13):341–358, 2014.</p>

<p>[MNT16] Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan. Near-optimal UGC-hardness of approximating Max $k$-CSP$_r$ . In Proceedings of the Workshop on Approximation Algorithms for Combinatorial Optimization Problems (to appear), 2016.</p>

CC BY-SA 3.0
2016-09-01T13:27:25.160Z
Thanks a lot for this very helpful answer! I have one more related question : Why are all analysis of CSP($\mathbb{F}_q$) in the Lasserre picture? Is there any reason why everyone has avoided a SOS program for this? I don't see anyone writing down a pseudoexpectation assignment which hits the thresholds. Or am I missing something?
gradstudent
CC BY-SA 3.0
2016-09-01T16:02:17.060Z
Lasserre = SOS. Previously (when some of the gaps for Max k-CSP_q were published), most researchers used the name “the Lasserre hierarchy”; these days, most researchers refer to it as “the SOS proof system”.
Yury
CC BY-SA 3.0
2016-09-02T14:45:53.327Z
But do we know that the Lasserre/SOS strong duality holds even over $\mathbb{F}_q$? (i.e when the pseudo-distribution is defined not over the Boolean hypercube but over the $\mathbb{F}_q^n$?) (Or is there an obvious way in which one can take the Lasserre certificate for Max-k-CSP($\mathbb{F}_q$) and re-write that as a pseudoexpectation assignment? Like for the $V_{(S,\alpha)}$ vectors in Madhur's analysis of Max-k-CSP($\mathbb{F}_q$) its not clear at all as to how to reproduce that in the pseudo-expectation language?)
gradstudent
CC BY-SA 3.0
2016-08-31T20:26:31.910Z
2016-08-31T20:50:30.217Z
2016-08-31T20:50:30.217Z
Yury
<p>I found two related papers,</p>

<ul>
<li><p>There is a UGC hardness result here, <a href="https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf">https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf</a> 
A kind of a stronger result might be found in these two other papers, <a href="http://www.csc.kth.se/~austrin/papers/maxkcsp_full.pdf">http://www.csc.kth.se/~austrin/papers/maxkcsp_full.pdf</a> and <a href="http://eccc.hpi-web.de/report/2012/110/download/">http://eccc.hpi-web.de/report/2012/110/download/</a></p></li>
<li><p>There is an approximation threshold with respect to Lasserre rounds here,
<a href="http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf">http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf</a> </p></li>
</ul>

<p>Are there other important papers in this topic? Like has anyone shown SOS hardness for this? (I don't see a way to dualize Madhur's Lasserre results to get that!) I would be glad to know what other papers in this topic should one look up. </p>

CC BY-SA 3.0
2017-07-04T15:25:13.213Z
Interesting question. Ok
Tayfun Pay
<reference-request><np-hardness><complexity-classes><approximation-hardness><csp>
What are the hardness results known for CSP over $\mathbb{F}_q$?
gradstudent
# What are the hardness results known for CSP over $\mathbb{F}_q$?

(Asked by: username_0 on 2016-08-30)

I found two related papers,

* There is a UGC hardness result here, <https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf>
  A kind of a stronger result might be found in these two other papers, <http://www.csc.kth.se/~austrin/papers/maxkcsp_full.pdf> and <http://eccc.hpi-web.de/report/2012/110/download/>
* There is an approximation threshold with respect to Lasserre rounds here,
  <http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf>

Are there other important papers in this topic? Like has anyone shown SOS hardness for this? (I don't see a way to dualize Madhur's Lasserre results to get that!) I would be glad to know what other papers in this topic should one look up.

**Tags:** reference-request, np-hardness, complexity-classes, approximation-hardness, csp

> **Comments:**
> **username_1**: Interesting question. Ok  

---

## 1 answers

### Answer by username_2 on 2016-08-31. Score: 8

Here is a summary of what is known about approximability of $k$-CSP over a domain of size $q$:

* The best known approximation algorithms for the problem give an $\Omega(q \max(k, \log q)/q^k)$ approximation [MM14 and MNT16].
* For $k = \Omega(q)$, there is a matching hardness of $O(kq/q^k)$ by Håstad (UGC-hardness) and Chan (NP-hardness) [Chan13].
* For $k$ between $c \log q / \log \log q$ and $q$, the best known NP-hardness result is $O(q^2/q^k)$ (follows from [Chan13]).
* For $2 < k < c \log q / \log \log q$, the best known UGC-hardness is $2^{O(k \log k)} q \, (\log q)^{k/2}/q^k$ by Manurangsi et al. [MNT16].
* For $k=2$, the best NP-hardness is $O(\log q/\sqrt{q})$ by Chan [Chan13], the best UGC-hardness is $O(\log q/q^k)$ by Khot et al. [KKMO07]

[Chan13] Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings of the Symposium on Theory of Computing, pages 447–456, 2013.

[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproxima bility results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007.

[MM14] Konstantin Makarychev and username_2 Makarychev. Approximation algorithm for non-Boolean Max $k$-CSP. Theory of Computing, 10(13):341–358, 2014.

[MNT16] Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan. Near-optimal UGC-hardness of approximating Max $k$-CSP$\_r$ . In Proceedings of the Workshop on Approximation Algorithms for Combinatorial Optimization Problems (to appear), 2016.

> **Comments:**
> **username_0**: Thanks a lot for this very helpful answer! I have one more related question : Why are all analysis of CSP($\mathbb{F}_q$) in the Lasserre picture? Is there any reason why everyone has avoided a SOS program for this? I don't see anyone writing down a pseudoexpectation assignment which hits the thresholds. Or am I missing something?  
> **username_2**: Lasserre = SOS. Previously (when some of the gaps for Max k-CSP_q were published), most researchers used the name “the Lasserre hierarchy”; these days, most researchers refer to it as “the SOS proof system”.  
> **username_0**: But do we know that the Lasserre/SOS strong duality holds even over $\mathbb{F}_q$? (i.e when the pseudo-distribution is defined not over the Boolean hypercube but over the $\mathbb{F}_q^n$?) (Or is there an obvious way in which one can take the Lasserre certificate for Max-k-CSP($\mathbb{F}_q$) and re-write that as a pseudoexpectation assignment? Like for the $V_{(S,\alpha)}$ vectors in Madhur's analysis of Max-k-CSP($\mathbb{F}_q$) its not clear at all as to how to reproduce that in the pseudo-expectation language?)  

---

