We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Suboptimality of local algorithms for a class of max-cut problems

Chen, Wei-Kuo and Gamarnik, David and Panchenko, Dmitry and Rahman, Mustazee (2019) 'Suboptimality of local algorithms for a class of max-cut problems.', Annals of probability., 47 (3). pp. 1587-1618.


We show that in random K -uniform hypergraphs of constant average degree, for even K ≥ 4 , local algorithms defined as factors of i.i.d. can not find nearly maximal cuts, when the average degree is sufficiently large. These algorithms have been used frequently to obtain lower bounds for the max-cut problem on random graphs, but it was not known whether they could be successful in finding nearly maximal cuts. This result follows from the fact that the overlap of any two nearly maximal cuts in such hypergraphs does not take values in a certain nontrivial interval—a phenomenon referred to as the overlap gap property—which is proved by comparing diluted models with large average degree with appropriate fully connected spin glass models and showing the overlap gap property in the latter setting.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Date accepted:25 May 2018
Date deposited:04 October 2021
Date of first online publication:02 May 2019
Date first made open access:04 October 2021

Save or Share this output

Look up in GoogleScholar