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

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 $η$-fraction of the nodes. We develop the first polynomial-time algorithm for this problem that estimates $d^\circ$ up to an additive error $O([\sqrt{\log(n) / n} + η\sqrt{\log(1/η)} ] \cdot \sqrt{d^\circ} + η\log(1/η))$. Our error guarantee matches information-theoretic lower bounds up to factors of $\log(1/η)$. Moreover, our estimator works for all $d^\circ \geq Ω(1)$ and achieves optimal breakdown point $η= 1/2$. Previous algorithms [AJK+22, CDHS24], including inefficient ones, incur significantly suboptimal errors. Furthermore, even admitting suboptimal error guarantees, only inefficient algorithms achieve optimal breakdown point. Our algorithm is based on the sum-of-squares (SoS) hierarchy. A key ingredient is to construct constant-degree SoS certificates for concentration of the number of edges incident to small sets in $G(n, d^\circ/n)$. Crucially, we show that these certificates also exist in the sparse regime, when $d^\circ = o(\log n)$, a regime in which the performance of previous algorithms was significantly suboptimal.