  In this paper we continue to rigorously establish the predictions in ground
breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborov\'a
(2011) regarding the block model, in particular in the case of $q=3$ and $q=4$
communities.
  We prove that for $q=3$ and $q=4$ there is no computational-statistical gap
if the average degree is above some constant by showing it is information
theoretically impossible to detect below the Kesten-Stigum bound. The proof is
based on showing that for the broadcast process on Galton-Watson trees,
reconstruction is impossible for $q=3$ and $q=4$ if the average degree is
sufficiently large. This improves on the result of Sly (2009), who proved
similar results for regular trees for $q=3$. Our analysis of the critical case
$q=4$ provides a detailed picture showing that the tightness of the
Kesten-Stigum bound in the antiferromagnetic case depends on the average degree
of the tree. We also prove that for $q\geq 5$, the Kestin-Stigum bound is not
sharp.
  Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborov\'a
(2011), Moore (2017), Abbe and Sandon (2018) and Ricci-Tersenghi, Semerjian,
and Zdeborov{\'a} (2019). Our proofs are based on a new general coupling of the
tree and graph processes and on a refined analysis of the broadcast process on
the tree.
