Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy
  We give a simple, computationally efficient, and node-differentially-private
algorithm for estimating the parameter of an Erdos-Renyi 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 on a small
interval.
