  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.
