Document Open Access Logo

From Weak to Strong LP Gaps for All CSPs

Authors Mrinalkanti Ghosh, Madhur Tulsiani

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.11.pdf
  • Filesize: 0.67 MB
  • 27 pages

Document Identifiers

Author Details

Mrinalkanti Ghosh
Madhur Tulsiani

Cite As Get BibTex

Mrinalkanti Ghosh and Madhur Tulsiani. From Weak to Strong LP Gaps for All CSPs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 11:1-11:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.11

Abstract

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by Omega(log(n)/log(log(n))) levels of the Sherali-Adams hierarchy on instances of size n. 

It was proved by Chan et al. [FOCS 2013] (and recently strengthened by Kothari et al. [STOC 2017]) that for CSPs, any polynomial size LP extended formulation is no stronger than relaxations obtained by a super-constant levels of the Sherali-Adams hierarchy. Combining this with our result also implies that any polynomial size LP extended formulation is no stronger than simply the basic LP, which can be thought of as the base level of the Sherali-Adams hierarchy. This essentially gives a dichotomy result for approximation of CSPs by polynomial size LP extended formulations.

Using our techniques, we also simplify and strengthen the result by Khot et al. [STOC 2014] on (strong) approximation resistance for LPs. They provided a necessary and sufficient condition under which Omega(loglog n) levels of the Sherali-Adams hierarchy cannot achieve an approximation better than a random assignment. We simplify their proof and strengthen the bound to Omega(log(n)/log(log(n))) levels.

Subject Classification

Keywords
  • Constraint Satisfaction Problem
  • Convex Programming
  • Linear Programming Hierarchy
  • Integrality Gap

Metrics

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

References

  1. Michael Alekhnovich, Sanjeev Arora, and Iannis Tourlakis. Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. In Proceedings of the 37th ACM Symposium on Theory of Computing, pages 294-303, 2005. Google Scholar
  2. Sanjeev Arora, Béla Bollobás, and László Lovász. Proving integrality gaps without knowing the linear program. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pages 313-322. IEEE, 2002. URL: http://dx.doi.org/10.1109/SFCS.2002.1181954.
  3. Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis. Proving integrality gaps without knowing the linear program. Theory of Computing, 2(2):19-51, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a002.
  4. Per Austrin and Johan Håstad. On the usefulness of predicates. ACM Trans. Comput. Theory, 5(1):1:1-1:24, May 2013. URL: http://dx.doi.org/10.1145/2462896.2462897.
  5. Boaz Barak, Siu On Chan, and Pravesh K. Kothari. Sum of squares lower bounds from pairwise independence. In Proceedings of the 47th ACM Symposium on Theory of Computing, pages 97-106, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746625.
  6. Eli Ben-Sasson. Expansion in Proof Complexity. PhD thesis, Hebrew University, 2001. Google Scholar
  7. Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. SDP gaps from pairwise independence. Theory of Computing, 8(12):269-289, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a012.
  8. Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. Approximate constraint satisfaction requires large LP relaxations. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science, pages 350-359, Washington, DC, USA, 2013. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2013.45.
  9. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin. Approximating a finite metric by a small number of tree metrics. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pages 379-388, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743488.
  10. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Local global tradeoffs in metric embeddings. In Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pages 713-723, Washington, DC, USA, 2007. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2007.37.
  11. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for maximum constraint satisfaction problems. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pages 62-68, 2007. URL: http://dx.doi.org/10.1145/1283383.1283391.
  12. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Integrality gaps for Sherali-Adams relaxations. In Proceedings of the 41st ACM Symposium on Theory of Computing, pages 283-292, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1536414.1536455.
  13. Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu. Linear programming relaxations of maxcut. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pages 53-61, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1283383.1283390.
  14. Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, and Rishi Saket. On the approximability of digraph ordering. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 792-803, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_66.
  15. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th ACM Symposium on Theory of Computing, pages 767-775, New York, NY, USA, 2002. ACM. URL: http://dx.doi.org/10.1145/509907.510017.
  16. Subhash Khot and Rishi Saket. SDP Integrality Gaps with Local 𝓁₁-Embeddability. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, pages 565-574, Washington, DC, USA, 2009. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2009.37.
  17. Subhash Khot and Rishi Saket. Approximating CSPs using LP relaxation. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, volume 9134, pages 822-833. Springer Verlag, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_67.
  18. Subhash Khot, Madhur Tulsiani, and Pratik Worah. A characterization of strong approximation resistance. In Proceedings of the 46th ACM Symposium on Theory of Computing, pages 634-643, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2591796.2591817.
  19. Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný. The power of linear programming for general-valued CSPs. SIAM Journal on Computing, 44(1):1-36, 2015. URL: http://dx.doi.org/10.1137/130945648.
  20. Pravesh Kothari, Raghu Meka, and Prasad Raghavendra. Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In Proceedings of the 49th ACM Symposium on Theory of Computing, 2017. (To appear). Google Scholar
  21. Pravesh Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th ACM Symposium on Theory of Computing, 2017. (To appear). Google Scholar
  22. Robert Krauthgamer, James R Lee, Manor Mendel, and Assaf Naor. Measured descent: A new embedding method for finite metrics. Geometric &Functional Analysis GAFA, 15(4):839-858, 2005. URL: http://dx.doi.org/10.1007/s00039-005-0527-6.
  23. Euiwoong Lee. Hardness of graph pricing through generalized max-dicut. In Proceedings of the 47th ACM Symposium on Theory of Computing, pages 391-399, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746549.
  24. L. Lovász and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM J. on Optimization, 1(12):166-190, 1991. URL: http://dx.doi.org/10.1137/0801013.
  25. Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th ACM Symposium on Theory of Computing, pages 245-254, New York, NY, USA, 2008. ACM. URL: http://dx.doi.org/10.1145/1374376.1374414.
  26. Prasad Raghavendra and David Steurer. Integrality gaps for strong SDP relaxations of unique games. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.73.
  27. Grant Schoenebeck. Linear level Lasserre lower bounds for certain k-CSPs. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, pages 593-602, Washington, DC, USA, 2008. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2008.74.
  28. Hanif D. Sherali and Warren P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math., 3(3):411-430, 1990. URL: http://dx.doi.org/10.1137/0403036.
  29. Johan Håstad. On the Efficient Approximability of Constraint Satisfaction Problems. In Surveys in Combinatorics, volume 346, pages 201-222. Cambridge University Press, 2007. URL: http://dx.doi.org/10.1017/CBO9780511666209.008.
  30. Johan Thapper and Stanislav Živný. The complexity of finite-valued CSPs. In Proceedings of the 45th ACM Symposium on Theory of Computing, pages 695-704, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2488608.2488697.
  31. Johan Thapper and Stanislav Živný. The power of Sherali-Adams relaxations for general-valued CSPs. arXiv preprint arXiv:1606.02577, 2016. Google Scholar
  32. Madhur Tulsiani. CSP gaps and reductions in the Lasserre hierarchy. In Proceedings of the 41st ACM Symposium on Theory of Computing, pages 303-312, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1536414.1536457.
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 About DROPS Imprint Privacy Contact