Local algorithms for independent sets are half-optimal

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.

Exposition has been clarified in the new version

References in corpus (2)

• Maximum independent sets on random regular graphs
• Invariant random matchings in Cayley graphs

Cited by in corpus (26)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Finding One Community in a Sparse Graph
• Suboptimality of local algorithms for a class of max-cut problems
• Computational Barriers to Estimation from Low-Degree Polynomials
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Optimizing Mean Field Spin Glasses with External Field
• The Overlap Gap Property in Principal Submatrix Recovery
• Factor of iid percolation on trees
• Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
• Entropy and expansion
• Improved replica bounds for the independence ratio of random regular graphs
• High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition
• Finding a Large Submatrix of a Gaussian Random Matrix
• On the Max-Cut of Sparse Random Graphs
• Sampling from Mean-Field Gibbs Measures via Diffusion Processes
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• Local Algorithms for Block Models with Side Information
• Local approximation of the Maximum Cut in regular graphs
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Correlation bound for distant parts of factor of IID processes
• How Well Do Local Algorithms Solve Semidefinite Programs?
• Ising model on trees and factors of IID