Limits of local algorithms over sparse random graphs

David Gamarnik, Madhu Sudan

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 inform…