Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
Authors: Jonathan Ullman, Adam Sealfon
NeurIPS 2019 | Venue PDF | 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 EMAIL Jonathan Ullman Northeastern University EMAIL |
| 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. |