Login
Talks & Seminars
Title: Limits of Local Algorithms Over Sparse Random Graphs
Prof. Madhu Sudan Principal Researcher Microsoft Research New England Cambridge, USA, Microsoft Research New England Cambridge, USA
Date & Time: October 7, 2014 16:00
Venue: Ramanujan Hall, Dept. of Mathematics
Abstract:
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 signi cant promise in computing structures like large independent sets in graphs locally. Indeed the promise led to a conjecture by Hatami, Lovasz, and Szegedy, that local algorithms may be able to compute maximum independent sets in (sparse) random d -regular graphs. In this talk we refute this conjecture and show that every independent set produced by local algorithms is multiplicative factor 1 = 2 + 1 = (2 p 2) smaller than the largest, asymptotically as d !1 . Our result is based on an important clustering phenomena predicted rst 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 speci c 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 signi cant 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 rst one where the clustering property is used to formally prove limits on local algorithms. Based on joint work with David Gamarnik
Speaker Profile:
Madhu Sudan received his bachelor's degree in computer science from IIT Delhi in 1987 and his doctoral degree in computer science at the University of California, Berkeley in 1992. He was a research staff member at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York from 1992 to 1997 and moved to MIT after that. Since June 2009, he's been at Microsoft Research New England as a permanent researcher. He was awarded the Rolf Nevanlinna Prize at the 24th International Congress of Mathematicians in 2002. The prize recognizes outstanding work in the mathematical aspects of computer science. He received the Gödel Prize in 2001. He is a Fellow of the ACM (2008). In 2012 he became a fellow of the American Mathematical Society. Sudan has made important contributions to several areas of theoretical computer science, including probabilistically checkable proofs, non-approximability of optimization problems, list decoding, and error-correcting codes.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback