Local algorithms for independent sets are half-optimal
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Feb 2014.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 1; 2023: 2; 2024: 0; 2025: 3; 2026: 2.
9 papers.
- 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
- 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
- 2022Rethinking Graph Neural Networks for the Graph Coloring Problemcited by 13
- 2025Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDTcited by 5
- 2025Binary perceptron computational gap -- a parametric fl RDT viewcited by 3
- 2025Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Setcited by 2
- 2023Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023replycited by 1
- 2026Parametric RDT approach to computational gap of symmetric binary perceptroncited by 1
- 2026Ultrametric OGP - parametric RDT symmetric binary perceptron connectioncited by 0
- 2026Ultrametric OGP - parametric RDT symmetric binary perceptron connection21 Apr 2026
- 2026Parametric RDT approach to computational gap of symmetric binary perceptron15 Jan 2026
- 2025Binary perceptron computational gap -- a parametric fl RDT view2 Nov 2025
- 2025Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT24 Jun 2025
- 2025Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set5 Feb 2025
- 2023Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023reply5 Jun 2023
- 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning8 Jan 2023
- 2022Rethinking Graph Neural Networks for the Graph Coloring Problem15 Aug 2022
- 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials3 Jun 2021