Local Algorithms for Graphs
  We are going to analyze local algorithms over sparse random graphs. These algorithms are based on local information where local regards to a decision made by the exploration of a small neighbourhood of a certain vertex plus a believe of the structure of the whole graph and maybe added some randomness. This kind of algorithms can be a natural response to the given problem or an efficient approximation such as the Belief Propagation Algorithm. 
David Gamarnik, Mathieu Hemery, Samuel Hetterich
cond-mat.dis-nn cs.DS