{"id":"arxiv/2610.09303","url":"https://arxiv.org/abs/2610.09303","tags":["math.ST","cs.IT"],"score":0,"title":"Tightness and Error Exponents of SDP with Logarithmically Many Communities","domain":"math.ST","source":"arxiv","authors":["Shengtao Guo","Ethan X. Fang","Junwei Lu"],"reviews":0,"subject":"math.ST","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}