2026-07-22T09:11:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10830 2024-03-06T10:46:49Z ddc:004 open_access

Sherali - Adams Strikes Back O'Donnell, Ryan Schramm, Tselil Linear programming Sherali Adams max-cut graph eigenvalues Sum-of-Squares 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ryan O'Donnell and Tselil Schramm 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.8 urn:nbn:de:0030-drops-108309 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.8 eng https://creativecommons.org/licenses/by/3.0/legalcode