# What are the hardness results known for CSP over $\mathbb{F}_q$?

I found two related papers,

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.

• Interesting question. Ok – Tayfun Pay Jul 4 '17 at 15:25

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 Yury 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.

• 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 Sep 1 '16 at 13:27
• 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 Sep 1 '16 at 16:02
• 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 Sep 2 '16 at 14:45