Local algorithms for independent sets are half-optimal

DOI10.1214/16-AOP1094zbMath1377.60049arXiv1402.0485MaRDI QIDQ2012245

Bálint Virág, Mustazee Rahman

Publication date: 28 July 2017

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.0485

zbMATH Keywords

independent setrandom regular graphsErdős-Rényi random graphslocal algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stationary stochastic processes (60G10) Combinatorial probability (60C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items (36)

Colouring graphs with forbidden bipartite subgraphs ⋮ Energy landscape for large average submatrix detection problems in Gaussian random matrices ⋮ Sparse high-dimensional linear regression. Estimating squared error and a phase transition ⋮ Total domination in regular graphs ⋮ Factor of IID Percolation on Trees ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Asymptotic bounds on total domination in regular graphs ⋮ The largest hole in sparse random graphs ⋮ Finding one community in a sparse graph ⋮ A factor of i.i.d. with uniform marginals and infinite clusters spanned by equal labels ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Suboptimality of local algorithms for a class of max-cut problems ⋮ On the almost eigenvectors of random regular graphs ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Borel fractional colorings of Schreier graphs ⋮ Improved replica bounds for the independence ratio of random regular graphs ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Shattering versus metastability in spin glasses ⋮ A tale of two balloons ⋮ Optimizing mean field spin glasses with external field ⋮ Spectral measures of factor of i.i.d. processes on vertex-transitive graphs ⋮ 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 ⋮ The overlap gap property and approximate message passing algorithms for \(p\)-spin models ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Entropy and expansion ⋮ Local approximation of the maximum cut in regular graphs ⋮ The overlap gap property in principal submatrix recovery ⋮ Mutual information decay for factors of i.i.d. ⋮ Ising model on trees and factors of IID ⋮ Entropy inequalities for factors of IID ⋮ Minimum 2-dominating sets in regular graphs ⋮ Walksat Stalls Well Below Satisfiability ⋮ Sofic homological invariants and the Weak Pinsker Property ⋮ Optimal low-degree hardness of maximum independent set

This page was built for publication: Local algorithms for independent sets are half-optimal