Limits of local algorithms over sparse random graphs

Madhu Sudan (Harvard)

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. 

On the one hand several works in the past decade have shown that such algorithms can be remarkably powerful and manage to compute fairly complex structures with low locality (using randomness). In this talk I will talk a bit about their limitations. In particular we borrow insights from the statistical physics literature to show that local algorithms can not compute very large independent sets even in random graphs. The insights from the statistical physics literature inidicate that the geometry of the solution space can be quite intricate for this problem on random graphs. We develop this insight to show a specific clustering property which shows that for most graphs 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.  This, along with basic properties of local algorithms allows us to conclude that such algorithms can not get very good approximations to independent sets is large random $d$-regular graphs. In particular this work refuted a conjecture of Hatami, Lovasz and Szegedy (Arxiv, 1205.4356).

Time permitting I will also talk about some strengthenings and follow up work.

Based on joint works with David Gamarnik (MIT).