Delphi.science

Optimal Robust Community Detection

Source: arxiv.org/abs/2611.25157

Samuel B. Hopkins, Yiding Hua, Sidhanth Mohanty, Amit Rajaraman, David Steurer

arXivarxiv/2611.25157Nov 18, 2026cs.DSscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.25157
curl -X POST /api/v1/records/arxiv/2611.25157/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.25157/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'