  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
\cite{HatamiLovaszSzegedy} 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$.
  Our result is based on an important clustering phenomena predicted first in
the literature on spin glasses, and recently proved rigorously for a variety of
constraint satisfaction problems on random graphs. Such properties suggest that
the geometry of the solution space can be quite intricate. The specific
clustering property, that we prove and apply in this paper shows that typically
every two large independent sets in a random graph either have a significant
intersection, or have a nearly empty intersection. As a result, large
independent sets are clustered according to the proximity to each other. While
the clustering property was postulated earlier as an obstruction for the
success of local algorithms, such as for example, the Belief Propagation
algorithm, our result is the first one where the clustering property is used to
formally prove limits on local algorithms.
