REVIEW 1 cited by
Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We give the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of Erd\H{o}s-R\'enyi random graphs and their generalization, inhomogeneous random graphs. We further prove information-theoretical lower bounds, showing that the error rate of our algorithm is optimal up to logarithmic factors. Previous algorithms incur either exponential running time or suboptimal error rates. Two key ingredients of our algorithm are (1) a new sum-of-squares algorithm for robust edge density estimation, and (2) the reduction from privacy to robustness based on sum-of-squares exponential mechanisms due to Hopkins et al. (STOC 2023).
Forward citations
Cited by 1 Pith paper
-
SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search
SubSearch uses simulated annealing to select a subgraph that best matches a stochastic block model, giving robust parameter estimates and outlier detection under node corruption.
Discussion (0). Sign in to comment.