Robust Parameter Estimation For Random Graphs
summary
Establishes nearly tight upper and lower bounds for estimating p in G(n,p) with an adversary corrupting a γ fraction of nodes: a two-step algorithm uses a spectral coarse estimate (top eigenvector to find and prune corrupted nodes) followed by degree trimming, achieving the non-robust rate Θ(√(p(1−p)/N)) plus an unavoidable robustness penalty that grows with γ (if γ is constant the error inflates by about a factor √N). Provides matching lower bound via coupling to directed G(n,p) and reports runtime ~ N^{2.5} (improvable to N^2).
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:43Talk overview
- 2:29Basic estimators
- 3:34Adversarial corruptions
- 5:04Robust estimation history
- 6:31Random graph estimation
- 7:13Pruning limitations
- 8:22Robust parameter results
- 12:18Algorithm overview
- 17:02Efficient pruning
- 19:32Lower bounds
- 21:46Directed graph reduction
- 22:08Conclusion
- 22:51Q&A
related talks
56mTesting Thresholds for High-dimensional Sparse Random Geometric Graphs
45mThe lower tail: Poisson approximation revisited
35mDistributed Models for Private Analysis of Graph Data
42mBootstrap Percolation on Random Graphs
49mExtremal Cuts of Sparse Random Graphs
35mContagious Sets in Random Graphs
49mRecent Advances in Counting Sparse Graphs
40mTesting Correlation of Unlabeled Random Graphs