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).
Bio: Madhu Sudan is a Gordon McKay Professor in the John A. Paulson School of Engineering and Applied Sciences at Harvard University, where he has been since 2015. Madhu Sudan got his Bachelors degree from IIT Delhi in 1987 and his Ph.D. from U.C. Berkeley in 1992. Between 1992 and 2015, Madhu Sudan worked at IBM Research (Research Staff Member 1992-1997), at MIT (Associate Professor 1997-2000, Professor 2000-2011, Fujitsu Chair Professor 2003-2011, CSAIL Associate Director 2007-2009, Adjunct Professor 2011-2015), and at Microsoft Research (Principal Researcher, 2009-2015). Madhu Sudan is a recipient of the Nevanlinna Prize awarded by the International Mathematical Union for outstanding contributions to mathematics of computer and information science, and the Infosys Foundation Prize in Mathematical Sciences. Madhu Sudan is a fellow of the Association for Computing Machinery, the Institute of Electrical and Electronics Engineers and the American Mathematical Society. He is a member of the American Academy of Arts and Sciences and the National Academy of Sciences.
Madhu Sudan's research interests revolve around mathematical studies of communication and computation. Specifically his research focusses on concepts of reliability and mechanisms that are, or can be, used by computers to interact reliably with each other. His research draws on tools from computational complexity, which studies efficiency of computation, and many areas of mathematics including algebra and probability theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. His current research interests include property testing which is the study of sublinear time algorithms to estimate properties of massive data, and communication amid uncertainty, a mathematical study of the role of context in communication.