Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR13-055 | 5th April 2013 16:18

#### Limits of local algorithms over sparse random graphs

TR13-055
Publication: 5th April 2013 16:19
Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research has shown that such algorithms show significant promise in computing structures like large independent sets in graphs locally. Indeed the promise led to a conjecture by Hatami, Lovasz and Szegedy [http://arxiv.org/abs/1205.4356] that local algorithms may be able to compute maximum independent sets in (sparse) random $d$-regular graphs. In this paper we refute this conjecture and show that every independent set produced by local algorithms is multiplicative factor $1/2+1/(2\sqrt{2})$ smaller than the largest, asymptotically as $d\rightarrow\infty$.