Research map / Federated learning and privacy / Differential privacy
Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
Jonathan Ullman, Adam Sealfon
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reweight edges incident on out-of-range-degree vertices and add noise calibrated to smooth sensitivity | Proposed edge-density estimator · Concentrated-degree graphs | mean squared error: O\left( \frac{k^2}{\eps^2 n^4} + \frac{1}{\eps^4 n^4} \right) | Improved |
Closest papers by meaning
- Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust (NeurIPS 2024 · similarity 0.92)
- Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point (NeurIPS 2025 · similarity 0.89)
- Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy (NeurIPS 2026 · similarity 0.88)
- Differentially Private Gomory-Hu Trees (NeurIPS 2025 · similarity 0.87)
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.85)
- Differentially Private Graph Diffusion with Applications in Personalized PageRanks (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
