Decomposing a network into communities (a partition of the vertices such that there is a significantly higher density of connections within groups than between groups) has been a subject of great interest in the network science community due to its numerous applications in data compression and machine learning. For many real networks, however, we do not know the "true" community labels, and so one way of assessing whether a community detection algorithm works well or not is to frame the task as an inference problem: there is a set of nodes with artificially assigned "ground truth" community labels, from which a network is created through some probabilistic generative process, and the goal is to recover this structure using only the network and the algorithm of interest. Intuitively, if a graph is too sparsely connected or it is generated from a noisy process, we should fail to recover partitions that are correlated with our artificial ground truth. In this talk I discuss an interesting phenomenon in which it suddenly (in terms of a control parameter) becomes impossible to recover the true communities in a graph, even when they are explicitly planted in its topology! This abrupt qualitative change in the difficulty of the community detection problem is characterized by a phase transition analogous to that in a generalized Potts model in statistical mechanics, which can be derived from a statistical physics perspective using a free energy approximation and the cavity method. I will also discuss future work in this area and its implications for nonconvex optimization.