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 Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-18 Page: https://delphi.science/r/arxiv/2611.25157 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…