  We study the optimization landscape of a smooth nonconvex program arising
from synchronization over the two-element group $\mathbf{Z}_2$, that is,
recovering $z_1, \dots, z_n \in \{\pm 1\}$ from (noisy) relative measurements
$R_{ij} \approx z_i z_j$. Starting from a max-cut--like combinatorial problem,
for integer parameter $r \geq 2$, the nonconvex problem we study can be viewed
both as a rank-$r$ Burer--Monteiro factorization of the standard max-cut
semidefinite relaxation and as a relaxation of $\{ \pm 1 \}$ to the unit sphere
in $\mathbf{R}^r$. First, we present deterministic, non-asymptotic conditions
on the measurement graph and noise under which every second-order critical
point of the nonconvex problem yields exact recovery of the ground truth. Then,
via probabilistic analysis, we obtain asymptotic guarantees for three benchmark
problems: (1) synchronization with a complete graph and Gaussian noise, (2)
synchronization with an Erd\H{o}s--R\'enyi random graph and Bernoulli noise,
and (3) graph clustering under the binary symmetric stochastic block model. In
each case, we have, asymptotically as the problem size goes to infinity, a
benign nonconvex landscape near a previously-established optimal threshold for
exact recovery; we can approach this threshold to arbitrary precision with
large enough (but finite) rank parameter $r$. In addition, our results are
robust to monotone adversaries.
