  In this work, we study the problem of community detection in the stochastic
block model with adversarial node corruptions. Our main result is an efficient
algorithm that can tolerate an $\epsilon$-fraction of corruptions and achieves
error $O(\epsilon) + e^{-\frac{C}{2} (1 \pm o(1))}$ where $C = (\sqrt{a} -
\sqrt{b})^2$ is the signal-to-noise ratio and $a/n$ and $b/n$ are the
inter-community and intra-community connection probabilities respectively.
These bounds essentially match the minimax rates for the SBM without
corruptions. We also give robust algorithms for $\mathbb{Z}_2$-synchronization.
At the heart of our algorithm is a new semidefinite program that uses global
information to robustly boost the accuracy of a rough clustering. Moreover, we
show that our algorithms are doubly-robust in the sense that they work in an
even more challenging noise model that mixes adversarial corruptions with
unbounded monotone changes, from the semi-random model.
