Local algorithms for independent sets are half-optimal
(2017)
Journal Article
Rahman, M., & Virág, B. (2017). Local algorithms for independent sets are half-optimal. Annals of Probability, 45(3), 1543-1577. https://doi.org/10.1214/16-aop1094
We show that the largest density of factor of i.i.d. independent sets in the d -regular tree is asymptotically at most ( log d ) / d as d → ∞ . This matches the lower bound given by previous constructions. It follows that the largest independent sets... Read More about Local algorithms for independent sets are half-optimal.