Metraipolis › archive › dc_d3ff67f1ade9

Tightness and Error Exponents of SDP with Logarithmically Many Communities — arXiv:2610.09303

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.09303
License (as archived)
CC0-1.0
Archived
2026-10-08T12:42:45.845Z
SHA-256 of the archived text
9be67d2120b2bb6c5f19ecec5b3cbccf83506542d6190a08749fd14c87afe8e7
Stable URL of this page
https://metraipolis.com/documento/dc_d3ff67f1ade9

How to cite

Tightness and Error Exponents of SDP with Logarithmically Many Communities — arXiv:2610.09303 — arXiv (en), https://arxiv.org/abs/2610.09303 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d3ff67f1ade9 (Metraipolis archive dc_d3ff67f1ade9, sha256 9be67d2120b2bb6c5f19ecec5b3cbccf83506542d6190a08749fd14c87afe8e7)
BibTeX
@misc{dcd3ff67f1ade9,
  title = {Tightness and Error Exponents of SDP with Logarithmically Many Communities — arXiv:2610.09303},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09303},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d3ff67f1ade9; sha256 9be67d2120b2bb6c5f19ecec5b3cbccf83506542d6190a08749fd14c87afe8e7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09303. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with $n=km$ vertices, we consider the regime $k/\log m\to\gamma>0$, with edge probabilities $\alpha\log m/m$ within communities and $\beta\log m/m$ across them, for fixed $\alpha>\beta>0$. We derive the sharp asymptotic tightness boundary away from critical cases. When rare vertices cause tightness to fail while the bulk remains spectrally stable, the normalized matrix error of every near-optimal solution still vanishes. We prove matching high-probability exponents for this error and the normalized optimal objective gain, governed by the same local correction that determines tightness. Throughout this spectrally stable region, a single SDP solve followed by explicit rounding and refinement achieves exact community recovery above the information-theoretic threshold. This guarantee holds even when the planted community matrix is not an optimal solution to the SDP.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.ST, nuovi lavori del giorno).
Categorie arXiv: Statistics Theory (math.ST) ; Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.09303 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:16:15.191Z dalla pagina https://arxiv.org/list/math.ST/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).