  In this paper, we study the problem of exact community recovery in general,
two-community block models considering both Bernoulli and Gaussian matrix
models, capturing the Stochastic Block Model, submatrix localization, and
$\mathbb{Z}_2$-synchronization as special cases. We also study the settings
where $side$ $information$ about community assignment labels is available,
modeled as passing the true labels through a noisy channel: either the binary
erasure channel (where some community labels are known while others are erased)
or the binary symmetric channel (where some labels are flipped). We provide a
unified analysis of the effect of side information on the information-theoretic
limits of exact recovery, generalizing prior works and extending to new
settings. Additionally, we design a simple but optimal spectral algorithm that
incorporates side information (when present) along with the eigenvectors of the
matrix observation. Using the powerful tool of entrywise eigenvector analysis
[Abbe, Fan, Wang, Zhong 2020], we show that our spectral algorithm can mimic
the so called $genie$-$aided$ $estimators$, where the $i^{\mathrm{th}}$
genie-aided estimator optimally computes the estimate of the $i^{\mathrm{th}}$
label, when all remaining labels are revealed by a genie. This perspective
provides a unified understanding of the optimality of spectral algorithms for
various exact recovery problems in a recent line of work.
