  We study a random graph model named the "block model" in statistics and the
"planted partition model" in theoretical computer science. In its simplest
form, this is a random graph with two equal-sized clusters, with a
between-class edge probability of $q$ and a within-class edge probability of
$p$.
  A striking conjecture of Decelle, Krzkala, Moore and Zdeborov\'a based on
deep, non-rigorous ideas from statistical physics, gave a precise prediction
for the algorithmic threshold of clustering in the sparse planted partition
model. In particular, if $p = a/n$ and $q = b/n$, $s=(a-b)/2$ and $p=(a+b)/2$
then Decelle et al.\ conjectured that it is possible to efficiently cluster in
a way correlated with the true partition if $s^2 > p$ and impossible if $s^2 <
p$. By comparison, the best-known rigorous result is that of Coja-Oghlan, who
showed that clustering is possible if $s^2 > C p \ln p$ for some sufficiently
large $C$.
  In a previous work, we proved that indeed it is information theoretically
impossible to to cluster if $s^2 < p$ and furthermore it is information
theoretically impossible to even estimate the model parameters from the graph
when $s^2 < p$. Here we complete the proof of the conjecture by providing an
efficient algorithm for clustering in a way that is correlated with the true
partition when $s^2 > p$. A different independent proof of the same result was
recently obtained by Laurent Massoulie.
