How Robust are Reconstruction Thresholds for Community Detection?
  The stochastic block model is one of the oldest and most ubiquitous models
for studying clustering and community detection. In an exciting sequence of
developments, motivated by deep but non-rigorous ideas from statistical
physics, Decelle et al. conjectured a sharp threshold for when community
detection is possible in the sparse regime. Mossel, Neeman and Sly and
Massoulie proved the conjecture and gave matching algorithms and lower bounds.
  Here we revisit the stochastic block model from the perspective of semirandom
models where we allow an adversary to make `helpful' changes that strengthen
ties within each community and break ties between them. We show a surprising
result that these `helpful' changes can shift the information-theoretic
threshold, making the community detection problem strictly harder. We
complement this by showing that an algorithm based on semidefinite programming
(which was known to get close to the threshold) continues to work in the
semirandom model (even for partial recovery). This suggests that algorithms
based on semidefinite programming are robust in ways that any algorithm meeting
the information-theoretic threshold cannot be.
  These results point to an interesting new direction: Can we find robust,
semirandom analogues to some of the classical, average-case thresholds in
statistics? We also explore this question in the broadcast tree model, and we
show that the viewpoint of semirandom models can help explain why some
algorithms are preferred to others in practice, in spite of the gaps in their
statistical performance on random models.
