Document Open Access Logo

Sherali - Adams Strikes Back

Authors Ryan O'Donnell, Tselil Schramm

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2019.8.pdf
  • Filesize: 0.71 MB
  • 30 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Linear programming
  • Theory of computation → Convex optimization
  • Theory of computation → Network optimization
Keywords
  • Linear programming
  • Sherali
  • Adams
  • max-cut
  • graph eigenvalues
  • Sum-of-Squares

Metrics

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

Abstract

Let G be any n-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by 1/sqrt{Delta} (for example, a random graph G of average degree Theta(Delta) typically has this property). We show that the exp(c (log n)/(log Delta))-round Sherali - Adams linear programming hierarchy certifies that the maximum cut in such a G is at most 50.1 % (in fact, at most 1/2 + 2^{-Omega(c)}). For example, in random graphs with n^{1.01} edges, O(1) rounds suffice; in random graphs with n * polylog(n) edges, n^{O(1/log log n)} = n^{o(1)} rounds suffice.
Our results stand in contrast to the conventional beliefs that linear programming hierarchies perform poorly for max-cut and other CSPs, and that eigenvalue/SDP methods are needed for effective refutation. Indeed, our results imply that constant-round Sherali - Adams can strongly refute random Boolean k-CSP instances with n^{ceil[k/2] + delta} constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.

Cite As Get BibTex

Ryan O'Donnell and Tselil Schramm. Sherali - Adams Strikes Back. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 8:1-8:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.8

Author Details

Ryan O'Donnell
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Tselil Schramm
  • Harvard University, Cambridge, MA, USA
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • O'Donnell, Ryan: Supported by NSF grants CCF-1618679, CCF-1717606. This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).
  • Schramm, Tselil: This work was supported by NSF grants CCF 1565264 and CNS 1618026.

Acknowledgements

We thank Luca Trevisan for helpful comments, and Boaz Barak for suggesting the title. We also thank the Schloss Dagstuhl Leibniz Center for Informatics (and more specifically the organizers of the CSP Complexity and Approximability workshop), as well as the Casa Mathemática Oaxaca (and more specifically the organizers of the Analytic Techniques in TCS workshop); parts of this paper came together during discussions at these venues. T.S. also thanks the Oberwolfach Research Institute for Mathematics (and the organizers of the Proof Complexity and Beyond workshop), the Simons Institute (and the organizers of the Optimization semester program), and the Banff International Research Station (and the organizers of the Approximation Algorithms and Hardness workshop) where she tried to prove the opposite of the results in this paper, as well as Sam Hopkins, with whom some of those efforts were made.

References

  1. Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis. Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. Computational Complexity, 20(4):615-648, 2011. URL: https://doi.org/10.1007/s00037-011-0027-z.
  2. Sarah R. Allen, Ryan O'Donnell, and David Witmer. How to Refute a Random CSP. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 689-708. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.48.
  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: https://doi.org/10.4086/toc.2006.v002a002.
  4. Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh Vempala. Local Versus Global Properties of Metric Spaces. SIAM J. Comput., 41(1):250-271, 2012. URL: https://doi.org/10.1137/090780304.
  5. Francisco Barahona and Ali Ridha Mahjoub. On the cut polytope. Math. Programming, 36(2):157-173, 1986. URL: https://doi.org/10.1007/BF02592023.
  6. Boaz Barak, Moritz Hardt, Thomas Holenstein, and David Steurer. Subsampling Mathematical Relaxations and Average-case Complexity. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 512-531. SIAM, 2011. URL: https://doi.org/10.1137/1.9781611973082.41.
  7. Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 428-437. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.53.
  8. Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding Semidefinite Programming Hierarchies via Global Correlation. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 472-481. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.95.
  9. Christoph Berkholz. The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  10. Colin R Blyth. Expected Absolute Error of the Usual Estimator of the Binomial Parameter. American Statistician, pages 155-157, 1980. Google Scholar
  11. Ravi Boppana. Eigenvalues and graph bisection: An average-case analysis. In 28th Annual Symposium on Foundations of Computer Science, pages 280-285. IEEE, 1987. Google Scholar
  12. Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal. Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput., 28(2):541-573, 1999. URL: https://doi.org/10.1137/S0097539795290805.
  13. Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. Approximate Constraint Satisfaction Requires Large LP Relaxations. J. ACM, 63(4):34:1-34:22, October 2016. URL: https://doi.org/10.1145/2811255.
  14. M Charikar and A Wirth. Maximizing quadratic programs: extending Grothendieck’s inequality. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 54-60. IEEE, 2004. Google Scholar
  15. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Integrality gaps for Sherali-Adams relaxations. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 283-292. ACM, 2009. URL: https://doi.org/10.1145/1536414.1536455.
  16. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Local Global Tradeoffs in Metric Embeddings. SIAM J. Comput., 39(6):2487-2512, 2010. URL: https://doi.org/10.1137/070712080.
  17. Nicholas Cook, Larry Goldstein, and Tobias Johnson. Size biased couplings and the spectral gap for random regular graphs. Ann. Probab., 46(1):72-125, 2018. URL: https://doi.org/10.1214/17-AOP1180.
  18. Wenceslas Fernandez de la Vega and Claire Mathieu. Linear Programming Relaxations of Maxcut. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 53-61, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1283383.1283390.
  19. Charles Delorme and Svatopluk Poljak. Laplacian eigenvalues and the maximum cut problem. Mathematical Programming, 62(1-3):557-574, 1993. Google Scholar
  20. Michel Marie Deza and Monique Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer, Heidelberg, 1997. URL: https://doi.org/10.1007/978-3-642-04295-9.
  21. William E Donath and Alan J Hoffman. Lower bounds for the partitioning of graphs. In Selected Papers Of Alan J Hoffman: With Commentary, pages 437-442. World Scientific, 2003. Google Scholar
  22. Uriel Feige and Robert Krauthgamer. The Probable Value of the Lovász-Schrijver Relaxations for Maximum Independent Set. SIAM J. Comput., 32(2):345-370, 2003. URL: https://doi.org/10.1137/S009753970240118X.
  23. Uriel Feige and Michael Langberg. The RPR 2 rounding technique for semidefinite programs. In International Colloquium on Automata, Languages, and Programming, pages 213-224. Springer, 2001. Google Scholar
  24. Uriel Feige and Eran Ofek. Spectral techniques applied to sparse random graphs. Random Structures Algorithms, 27(2):251-275, 2005. URL: https://doi.org/10.1002/rsa.20089.
  25. Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298-305, 1973. Google Scholar
  26. Joel Friedman, Andreas Goerdt, and Michael Krivelevich. Recognizing More Unsatisfiable Random k-SAT Instances Efficiently. SIAM J. Comput., 35(2):408-430, 2005. URL: https://doi.org/10.1137/S009753970444096X.
  27. Joel Friedman, Jeff Kahn, and Endre Szemerédi. On the second eigenvalue of random regular graphs. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 587-598, 1989. Google Scholar
  28. Alan Frieze and Ravi Kannan. The regularity lemma and approximation schemes for dense problems. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 12-20. IEEE, 1996. Google Scholar
  29. Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6):1115-1145, 1995. URL: https://doi.org/10.1145/227683.227684.
  30. Andreas Goerdt and Michael Krivelevich. Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods. In Afonso Ferreira and Horst Reichel, editors, STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings, volume 2010 of Lecture Notes in Computer Science, pages 294-304. Springer, 2001. URL: https://doi.org/10.1007/3-540-44693-1_26.
  31. Dima Grigoriev. Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor. Comput. Sci., 259(1-2):613-622, 2001. URL: https://doi.org/10.1016/S0304-3975(00)00157-2.
  32. Johan Håstad. An NP-complete problem - some aspects of its solution and some possible applications. Master’s thesis, Uppsala University, 1984. Google Scholar
  33. Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The Power of Sum-of-Squares for Detecting Hidden Structures. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 720-731. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.72.
  34. Pravesh Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pages 132-145, 2017. Google Scholar
  35. Pravesh K. 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 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 590-603, 2017. URL: https://doi.org/10.1145/3055399.3055438.
  36. David A. Levin and Yuval Peres. Counting walks and graph homomorphisms via Markov chains and importance sampling. Amer. Math. Monthly, 124(7):637-641, 2017. URL: https://doi.org/10.4169/amer.math.monthly.124.7.637.
  37. Bojan Mohar and Svatopluk Poljak. Eigenvalues in combinatorial optimization. In Combinatorial and graph-theoretical problems in linear algebra, pages 107-151. Springer, 1993. Google Scholar
  38. Svatopluk Poljak. Polyhedral and eigenvalue approximations of the max-cut problem. In Sets, graphs and numbers (Budapest, 1991), volume 60 of Colloq. Math. Soc. János Bolyai, pages 569-581. North-Holland, Amsterdam, 1992. Google Scholar
  39. Svatopluk Poljak and Zsolt Tuza. The expected relative error of the polyhedral approximation of the max-cut problem. Oper. Res. Lett., 16(4):191-198, 1994. URL: https://doi.org/10.1016/0167-6377(94)90068-X.
  40. Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 121-131, 2017. URL: https://doi.org/10.1145/3055399.3055417.
  41. Prasad Raghavendra, Tselil Schramm, and David Steurer. High-dimensional estimation via sum-of-squares proofs. CoRR, abs/1807.11419, 2018. URL: http://arxiv.org/abs/1807.11419.
  42. Prasad Raghavendra and Ning Tan. Approximating CSPs with global cardinality constraints using SDP hierarchies. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 373-387. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.
  43. Grant Schoenebeck. Linear Level Lasserre Lower Bounds for Certain k-CSPs. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 593-602. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.74.
  44. Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani. Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 302-310. ACM, 2007. URL: https://doi.org/10.1145/1250790.1250836.
  45. 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: https://doi.org/10.1137/0403036.
  46. Konstantin Tikhomirov and Pierre Youssef. The spectral gap of dense random regular graphs. arXiv preprint, 2016. URL: http://arxiv.org/abs/1610.01765.
  47. Luca Trevisan. Max Cut and the Smallest Eigenvalue. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC '09, pages 263-272, New York, NY, USA, 2009. ACM. URL: https://doi.org/10.1145/1536414.1536452.
  48. Joel Tropp. An introduction to matrix concentration inequalities. Foundations and Trendsin Machine Learning, 8(1-2):1-230, 2015. Google Scholar
  49. Yuichi Yoshida and Yuan Zhou. Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 423-438. ACM, 2014. Google Scholar
  50. Uri Zwick. Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC '99, pages 679-687, New York, NY, USA, 1999. ACM. URL: https://doi.org/10.1145/301250.301431.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact