# Large independent sets on random d-regular graphs with fixed degree d

arXiv: https://arxiv.org/abs/2003.12293 · HTML: https://mlsanity.com/paper/2003.12293/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2020.

## Built on by (most cited first, 4 of 4)

- [Complex Recurrent Spectral Network](https://mlsanity.com/paper/2312.07296/) (2023)
- [Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems](https://mlsanity.com/paper/2309.05337/) (2023)
- [Engineered Ordinary Differential Equations as Classification Algorithm (EODECA): thorough characterization and testing](https://mlsanity.com/paper/2312.14681/) (2023)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)

## Abstract (arXiv)

This paper presents a linear prioritized local algorithm that computes large independent sets on a random d-regular graph with small and fixed degree d. We studied experimentally the independence ratio obtained by the algorithm when  d ∈ [3,100]. For all d ∈ [5,100], our results are larger than lower bounds calculated by exact methods, thus providing improved estimates of lower bounds.