Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
Authors: Jonathan Ullman, Adam Sealfon
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a simple, computationally efficient, and node-differentially-private algorithm for estimating the parameter of an Erd os-Rényi graph that is, estimating p in a G(n, p) with near-optimal accuracy. Our algorithm nearly matches the information-theoretically optimal exponential-time algorithm for the same problem due to Borgs et al. (FOCS 2018). More generally, we give an optimal, computationally efficient, private algorithm for estimating the edge-density of any graph whose degree distribution is concentrated in a small interval. |
| Researcher Affiliation | Academia | Adam Sealfon MIT and UC Berkeley asealfon@berkeley.edu Jonathan Ullman Northeastern University jullman@ccs.neu.edu |
| Pseudocode | Yes | Algorithm 1: Estimating the edge density of a concentrated-degree graph. Algorithm 2: Estimating the parameter of an Erd os-Rényi graph. |
| Open Source Code | No | The paper does not provide any links or explicit statements about the release of its source code. |
| Open Datasets | No | The paper describes theoretical models (Erd os-Rényi graphs) and algorithms, focusing on mathematical analysis and proofs. It does not conduct empirical experiments using specific datasets, thus no access information for a training dataset is provided. |
| Dataset Splits | No | The paper describes theoretical models and algorithms, not empirical experiments, thus no information on validation splits is relevant or provided. |
| Hardware Specification | No | The paper focuses on theoretical analysis and algorithm design, not empirical experiments requiring specific hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical analysis and algorithm design, not empirical experiments requiring specific software dependencies and versions. |
| Experiment Setup | No | The paper focuses on theoretical analysis and algorithm design, not empirical experiments requiring specific hyperparameter values or training configurations. |