Document Open Access Logo

Near-Optimal UGC-hardness of Approximating Max k-CSP_R

Authors Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.15.pdf
  • Filesize: 0.63 MB
  • 28 pages

Document Identifiers

Author Details

Pasin Manurangsi
Preetum Nakkiran
Luca Trevisan

Cite AsGet BibTex

Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan. Near-Optimal UGC-hardness of Approximating Max k-CSP_R. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 15:1-15:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.15

Abstract

In this paper, we prove an almost-optimal hardness for Max k-CSP_R based on Khot's Unique Games Conjecture (UGC). In Max k-CSP_R, we are given a set of predicates each of which depends on exactly k variables. Each variable can take any value from 1, 2, ..., R. The goal is to find an assignment to variables that maximizes the number of satisfied predicates. Assuming the Unique Games Conjecture, we show that it is NP-hard to approximate Max k-CSP_R to within factor 2^{O(k log k)}(log R)^{k/2}/R^{k - 1} for any k, R. To the best of our knowledge, this result improves on all the known hardness of approximation results when 3 <= k = o(log R/log log R). In this case, the previous best hardness result was NP-hardness of approximating within a factor O(k/R^{k-2}) by Chan. When k = 2, our result matches the best known UGC-hardness result of Khot, Kindler, Mossel and O'Donnell. In addition, by extending an algorithm for Max 2-CSP_R by Kindler, Kolla and Trevisan, we provide an Omega(log R/R^{k - 1})-approximation algorithm for Max k-CSP_R. This algorithm implies that our inapproximability result is tight up to a factor of 2^{O(k \log k)}(\log R)^{k/2 - 1}. In comparison, when 3 <= k is a constant, the previously known gap was $O(R)$, which is significantly larger than our gap of O(polylog R). Finally, we show that we can replace the Unique Games Conjecture assumption with Khot's d-to-1 Conjecture and still get asymptotically the same hardness of approximation.
Keywords
  • inapproximability
  • unique games conjecture
  • constraint satisfaction problem
  • invariance principle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. J. ACM, 62(5):42, 2015. URL: http://dx.doi.org/10.1145/2775105.
  2. P. Austrin and E. Mossel. Approximation resistant predicates from pairwise independence. In Computational Complexity, 2008. CCC'08. 23rd Annual IEEE Conference on, pages 249-258, June 2008. URL: http://dx.doi.org/10.1109/CCC.2008.20.
  3. Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC'13, pages 447-456, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2488608.2488665.
  4. Moses Charikar, MohammadTaghi Hajiaghayi, and Howard Karloff. Improved approximation algorithms for label cover problems. Algorithmica, 61(1):190-206, 2011. URL: http://dx.doi.org/10.1007/s00453-010-9464-3.
  5. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for unique games. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC'06, pages 205-214, New York, NY, USA, 2006. ACM. URL: http://dx.doi.org/10.1145/1132516.1132547.
  6. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for maximum constraint satisfaction problems. ACM Transactions on Algorithms, 5(3), 2009. URL: http://dx.doi.org/10.1145/1541885.1541893.
  7. Eden Chlamtac, Konstantin Makarychev, and Yury Makarychev. How to play unique games using embeddings. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 687-696, 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.36.
  8. Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan. On weighted vs unweighted versions of combinatorial optimization problems. Information and Computation, 167(1):10-26, 2001. Google Scholar
  9. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM Journal on Computing, 39(3):843-873, 2009. URL: http://dx.doi.org/10.1137/07068062X.
  10. Irit Dinur and Igor Shinkar. On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors. In Proceedings of the 13th International Conference on Approximation, and 14 the International Conference on Randomization, and Combinatorial Optimization: Algorithms and Techniques, APPROX/RANDOM'10, pages 138-151, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1886521.1886533.
  11. Lars Engebretsen. The nonapproximability of non-boolean predicates. SIAM J. Discret. Math., 18(1):114-129, January 2005. URL: http://dx.doi.org/10.1137/S0895480100380458.
  12. Lars Engebretsen and Jonas Holmerin. More efficient queries in pcps for np and improved approximation hardness of maximum csp. Random Struct. Algorithms, 33(4):497-514, December 2008. URL: http://dx.doi.org/10.1002/rsa.v33:4.
  13. Uriel Feige and Daniel Reichman. On systems of linear equations with two variables per equation. In Klaus Jansen, Sanjeev Khanna, JoséD.P. Rolim, and Dana Ron, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 3122 of Lecture Notes in Computer Science, pages 117-127. Springer Berlin Heidelberg, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27821-4_11.
  14. Gil Goldshlager and Dana Moshkovitz. Approximating kCSP for large alphabets. https://people.csail.mit.edu/dmoshkov/papers/Approximating%20MAX%20kCSP.pdf, 2015.
  15. Anupam Gupta and Kunal Talwar. Approximating unique games. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 99-106, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109569.
  16. Venkatesan Guruswami and Prasad Raghavendra. Constraint satisfaction over a non-boolean domain: Approximation algorithms and unique-games hardness. In Ashish Goel, Klaus Jansen, JoséD.P. Rolim, and Ronitt Rubinfeld, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, volume 5171 of Lecture Notes in Computer Science, pages 77-90. Springer Berlin Heidelberg, 2008. URL: http://dx.doi.org/10.1007/978-3-540-85363-3_7.
  17. Venkatesan Guruswami and Ali Kemal Sinop. The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1615-1626, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.125.
  18. Gustav Hast. Approximating Max kCSP - outperforming a random assignment with almost a linear factor. In Proceedings of the 32Nd International Conference on Automata, Languages and Programming, ICALP'05, pages 956-968, Berlin, Heidelberg, 2005. Springer-Verlag. URL: http://dx.doi.org/10.1007/11523468_77.
  19. Johan Håstad. Clique is hard to approximate within n^1-ε. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 627-636. IEEE, 1996. Google Scholar
  20. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-fourth Annual ACM Symposium on Theory of Computing, STOC'02, pages 767-775, New York, NY, USA, 2002. ACM. URL: http://dx.doi.org/10.1145/509907.510017.
  21. Subhash Khot. On the unique games conjecture (invited survey). In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, pages 99-121, 2010. URL: http://dx.doi.org/10.1109/CCC.2010.19.
  22. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable csps? SIAM J. Comput., 37(1):319-357, 2007. URL: http://dx.doi.org/10.1137/S0097539705447372.
  23. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci., 74(3):335-349, May 2008. URL: http://dx.doi.org/10.1016/j.jcss.2007.06.019.
  24. Guy Kindler, Alexandra Kolla, and Luca Trevisan. Approximation of non-boolean 2csp. CoRR, abs/1504.00681, 2015. URL: http://arxiv.org/abs/1504.00681.
  25. Alexandra Kolla. Spectral algorithms for unique games. Computational Complexity, 20(2):177-206, 2011. URL: http://dx.doi.org/10.1007/s00037-011-0011-7.
  26. Konstantin Makarychev and Yury Makarychev. Approximation algorithm for non-boolean max-k-csp. Theory of Computing, 10:341-358, 2014. URL: http://dx.doi.org/10.4086/toc.2014.v010a013.
  27. Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Ann. Math. (2), 171(1):295-341, 2010. URL: http://dx.doi.org/10.4007/annals.2010.171.295.
  28. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/analysis-boolean-functions.
  29. Ryan O'Donnell and Yi Wu. 3-bit dictator testing: 1 vs. 5/8. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 365-373, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496811.
  30. Ryan O'Donnell and Yi Wu. Conditional hardness for satisfiable 3-csps. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 493-502, 2009. URL: http://dx.doi.org/10.1145/1536414.1536482.
  31. Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC'08, pages 245-254, New York, NY, USA, 2008. ACM. URL: http://dx.doi.org/10.1145/1374376.1374414.
  32. Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 191-199, 2000. URL: http://dx.doi.org/10.1145/335305.335329.
  33. Alex Samorodnitsky and Luca Trevisan. Gowers uniformity, influence of variables, and pcps. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC'06, pages 11-20, New York, NY, USA, 2006. ACM. URL: http://dx.doi.org/10.1145/1132516.1132519.
  34. Linqing Tang. Conditional hardness of approximating satisfiable max 3csp-q. In Yingfei Dong, Ding-Zhu Du, and Oscar Ibarra, editors, Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science, pages 923-932. Springer Berlin Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-642-10631-6_93.
  35. Luca Trevisan. Parallel approximation algorithms by positive linear programming. Algorithmica, 21(1):72-88, 1998. URL: http://dx.doi.org/10.1007/PL00009209.
  36. Luca Trevisan. Approximation algorithms for unique games. Theory of Computing, 4(1):111-128, 2008. URL: http://dx.doi.org/10.4086/toc.2008.v004a005.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact