David Gamarnik (MIT) : Local Algorithms for Random Networks.
"Local Algorithms for Random Networks. Lecture I: the Power of Local
"Local Algorithms for Random Networks. Lecture II: the Limits of Local
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.