Tightness and Error Exponents of SDP with Logarithmically Many Communities
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γ>0$, with edge probabilities $α\log m/m$ within communities and $β\log m/m$ across them, for fixed $α>β>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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.09303
curl -X POST /api/v1/records/arxiv/2610.09303/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.09303/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'