Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author David Gamarnik:

TR13-055 | 5th April 2013
David Gamarnik, Madhu Sudan

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 randomness. Recent research ... more >>>

ISSN 1433-8092 | Imprint