{"id":"arxiv/2611.25157","url":"https://arxiv.org/abs/2611.25157","tags":["cs.DS","math.PR"],"score":0,"title":"Optimal Robust Community Detection","domain":"cs.DS","source":"arxiv","authors":["Samuel B. Hopkins","Yiding Hua","Sidhanth Mohanty","Amit Rajaraman","David Steurer"],"reviews":0,"subject":"cs.DS","summary":"We study community detection in the sparse two-community stochastic block model when an adversary may corrupt a small constant fraction of the edges of the observed graph. For every choice of parameters above the Kesten-Stigum threshold and every $\\varepsilon > 0$, we give a nearly-linear-time algorithm which estimates the communities with accuracy within $\\varepsilon$ of the information-theoretically optimal accuracy, while tolerating a small constant fraction of adversarially corrupted edges. Previously, efficient algorithms with optimal accuracy were known only in the absence of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-18","reactions":{}}