Limits of local algorithms for sparse random graphs

Algorithms which can be run in parallel on large networks based on local information (local algorithms) gained a lot of prominence recently in a variety of applications, primarily as a way of addressing the scaling issues for computations on large instances. Some local algorithms such as, for example, the Belief Propagation algorithm emerged as strong contenders for solving a variety of optimization and inference problems on large scale network models, including random instances of hard constraint satisfaction problems. In this talk we will discuss limitations of local algorithms for solving constraint satisfaction problems on random graphs. In particular, we will discuss a negative resolution of a recent conjecture regarding the power of local algorithms for solving largest independent set problem on random graphs. [Joint work with Madhu Sudan]