7
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Interesting question. Ok $\endgroup$
    – Tayfun Pay
    Jul 4, 2017 at 15:25

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – gradstudent
    Sep 1, 2016 at 13:27
  • $\begingroup$ 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”. $\endgroup$
    – Yury
    Sep 1, 2016 at 16:02
  • $\begingroup$ 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?) $\endgroup$
    – gradstudent
    Sep 2, 2016 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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