In this paper, we rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborová (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 that it is information theoretically impossible to detect below the Kesten-Stigum bound. We proceed by 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 d-regular trees when 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 regime depends on the average degree of the tree. We also prove that for q≥ 5, the Kesten-Stigum bound is not sharp. Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborová (2011), Moore (2017), Abbe and Sandon (2018) and Ricci-Tersenghi, Semerjian, and Zdeborová (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.