Limits of local algorithms over sparse random graphs
From MaRDI portal
Publication:5920116
DOI10.1214/16-AOP1114zbMath1371.05265arXiv1304.1831WikidataQ124831942 ScholiaQ124831942MaRDI QIDQ5920116
Publication date: 5 October 2017
Published in: The Annals of Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.1831
Related Items
Sparse high-dimensional linear regression. Estimating squared error and a phase transition, Disordered systems insights on computational hardness, Properties of regular graphs with large girth via local algorithms, The largest hole in sparse random graphs, Suboptimality of local algorithms for a class of max-cut problems, Algorithmic obstructions in the random number partitioning problem, Large Deviation Principle for the Greedy Exploration Algorithm over Erd\"os-R\'enyi Graphs, Shattering versus metastability in spin glasses, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, Limits of locally-globally convergent graph sequences, The overlap gap property and approximate message passing algorithms for \(p\)-spin models, Constructing concrete hard instances of the maximum independent set problem, Weak containment of measure-preserving group actions, Ising model on trees and factors of IID, Optimal low-degree hardness of maximum independent set
