Limits of local algorithms over sparse random graphs

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 randomnes...

Full description

Bibliographic Details
Main Authors: Gamarnik, David, Sudan, Madhu
Other Authors: Sloan School of Management
Format: Article
Language:en_US
Published: Association for Computing Machinery 2014
Online Access:http://hdl.handle.net/1721.1/87683
https://orcid.org/0000-0001-8898-8778