Global synchronization with negative edges
Call a matrix $A \in \mathbb{R}^{n \times n}$ globally synchronizing if the only local minima of $$\mathcal{E}(\theta) = \frac12\sum_{i,j=1}^n A_{ij}\bigl(1-\cos(\theta_i-\theta_j)\bigr), \qquad \theta \in [0,2\pi)^n,$$ are its global minima $\theta_1 = \dots = \theta_n$. The question comes from the Burer–Monteiro approach to community detection in the stochastic block model; McRae, Abdalla, Bandeira and Boumal answered a high-rank version.
Problem. Prove or disprove that, given any $\varepsilon > 0$, the $n \times n$ random matrix $A$ with zero diagonal and off-diagonal entries $$A_{ij} = \begin{cases} 1 & \text{with probability } \frac12 + \delta,\\ -1 & \text{with probability } \frac12 - \delta, \end{cases}$$ with $\delta \ge (1 + \varepsilon)\sqrt{\frac{\log n}{2n}}$, is globally synchronizing with high probability.
Source: Bandeira, Conjecture 4 of Randomstrasse101, in “Global Synchronization” (2024); Entry 2 of arXiv:2504.20539.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- PR — Probability
- Secondary
- OC
- Keywords
- Burer–Monteiro, community detection, global synchronization, Kuramoto model, Randomstrasse101
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2024,
author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2024},
year = {2025},
eprint = {2504.20539},
archivePrefix = {arXiv}
}
@inproceedings{bandeira2016lowrank,
author = {Bandeira, Afonso S. and Boumal, Nicolas and Voroninski, Vladislav},
title = {On the low-rank approach for semidefinite programs arising in synchronization and community detection},
booktitle = {Conference on Learning Theory (COLT 2016)},
year = {2016}
}
@misc{mcrae2024nonconvex,
author = {McRae, Andrew D. and Abdalla, Pedro and Bandeira, Afonso S. and Boumal, Nicolas},
title = {Nonconvex landscapes for {$\mathbb{Z}_2$} synchronization and graph clustering are benign near exact recovery thresholds},
year = {2024},
eprint = {2407.13407},
archivePrefix = {arXiv}
}
@misc{mcrae2025benign,
author = {McRae, Andrew D.},
title = {Benign landscapes for synchronization on spheres via normalized {L}aplacian matrices},
year = {2025},
eprint = {2503.18801},
archivePrefix = {arXiv}
}
Resolution claims
We study the nonconvex optimization landscapes of synchronization problems on spheres. First, we present new results for the statistical problem of synchronization over the two-element group $\mathbf{Z}_2$. We consider the nonconvex least-squares problem with $\mathbf{Z}_2 = \{\pm 1\}$ relaxed to the unit sphere in $\mathbf{R}^r$ for $r \geq 2$; for several popular models, including graph clustering under the binary stochastic …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-02 | Open → Solution claimed | The registry's curators | Benign landscapes for synchronization on spheres via normalized Laplacian matrices v1 recorded from arXiv:2503.18801v2. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00052, "Global synchronization with negative edges", clopen.solutions.