David Gamarnik (MIT) : Local Algorithms for Random Networks.

"Local Algorithms for Random Networks. Lecture I: the Power of Local Algorithms".

"Local Algorithms for Random Networks. Lecture II: the Limits of Local Algorithms".

In the first lecture we will discuss positive results for several examples of local algorithms, including local algorithms known as i.i.d. Factors, Belief Propagation and Cavity Expansion. The correlation decay property will be discussed as the principal reason for the success of these algorithms. In the second lecture we will discuss the limits of local algorithms in the context of random graphs and the fascinating connection with the so-called shattering property established for a variety of random constraint satisfaction problems.