O'Donnell, Ryan ;
Schramm, Tselil
Sherali  Adams Strikes Back
Abstract
Let G be any nvertex 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 maxcut and other CSPs, and that eigenvalue/SDP methods are needed for effective refutation. Indeed, our results imply that constantround Sherali  Adams can strongly refute random Boolean kCSP instances with n^{ceil[k/2] + delta} constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.
BibTeX  Entry
@InProceedings{odonnell_et_al:LIPIcs:2019:10830,
author = {Ryan O'Donnell and Tselil Schramm},
title = {{Sherali  Adams Strikes Back}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {8:18:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10830},
URN = {urn:nbn:de:0030drops108309},
doi = {10.4230/LIPIcs.CCC.2019.8},
annote = {Keywords: Linear programming, Sherali, Adams, maxcut, graph eigenvalues, SumofSquares}
}
2019
Keywords: 

Linear programming, Sherali, Adams, maxcut, graph eigenvalues, SumofSquares 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 