Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point

Hongjie Chen, Jingqiu Ding, Yiding Hua +1

We study the problem of robustly estimating the edge density of Erdős-Rényi random graphs $G(n,d^{\circ }/n)$ when an adversary can arbitrarily add or remove edges incident to an $\eta$…