Local algorithms for independent sets are half-optimal
From MaRDI portal
Publication:2012245
Abstract: We show that the largest density of factor of i.i.d. independent sets on the d-regular tree is asymptotically at most (log d)/d as d tends to infinity. This matches the lower bound given by previous constructions. It follows that the largest independent sets given by local algorithms on random d-regular graphs have the same asymptotic density. In contrast, the density of the largest independent sets on these graphs is asymptotically 2(log d)/d. We also prove analogous results for Poisson-Galton-Watson trees, which yield bounds for local algorithms on sparse Erdos-Renyi graphs.
Recommendations
- Limits of local algorithms over sparse random graphs
- Limits of local algorithms over sparse random graphs
- Large independent sets in random regular graphs
- Local algorithms, regular graphs of large girth, and random regular graphs
- Locally dense independent sets in regular graphs of~large~girth -- an example of a new approach
Cited in
(48)- Optimal Randomized Algorithms for Local Sorting and Set-Maxima
- Energy landscape for large average submatrix detection problems in Gaussian random matrices
- Local approximation of the maximum cut in regular graphs
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- Colouring graphs with forbidden bipartite subgraphs
- Shattering versus metastability in spin glasses
- Brief Announcement
- Factor of iid percolation on trees
- A factor of i.i.d. with uniform marginals and infinite clusters spanned by equal labels
- Borel fractional colorings of Schreier graphs
- Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem
- Improved replica bounds for the independence ratio of random regular graphs
- A tale of two balloons
- Cryptography from planted graphs: security with logarithmic-size messages
- Entropy and expansion
- Sofic homological invariants and the weak Pinsker property
- Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
- The landscape of the planted clique problem: dense subgraphs and the overlap gap property
- Total domination in regular graphs
- Asymptotic bounds on total domination in regular graphs
- Simple and local independent set approximation
- Optimizing mean field spin glasses with external field
- Optimal low-degree hardness of maximum independent set
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- Mutual information decay for factors of i.i.d.
- Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
- The overlap gap property and approximate message passing algorithms for \(p\)-spin models
- Local algorithms, regular graphs of large girth, and random regular graphs
- Large independent sets in random regular graphs
- Correlation bounds for distant parts of factor of IID processes
- On the almost eigenvectors of random regular graphs
- Tight Lipschitz hardness for optimizing mean field spin glasses
- Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs
- Algorithmic obstructions in the random number partitioning problem
- Limits of local algorithms over sparse random graphs
- Suboptimality of local algorithms for a class of max-cut problems
- Greedy maximal independent sets via local limits
- The largest hole in sparse random graphs
- The overlap gap property in principal submatrix recovery
- Walksat Stalls Well Below Satisfiability
- Ising model on trees and factors of IID
- On perfectly friendly bisections of random graphs
- Entropy inequalities for factors of IID
- Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
- Computational barriers to estimation from low-degree polynomials
- Finding one community in a sparse graph
- Minimum 2-dominating sets in regular graphs
- Free Energy Wells and Overlap Gap Property in Sparse PCA
This page was built for publication: Local algorithms for independent sets are half-optimal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012245)
