---
res:
  bibo_abstract:
  - "Differentially private algorithms protect individuals in data analysis scenarios
    by ensuring that there is only a weak correlation between the existence of the
    user in the data and the result of the analysis. Dynamic graph algorithms maintain
    the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph
    where nodes or edges are inserted or deleted over time. They output the value
    of the solution after each update operation, i.e., continuously. We study (event-level
    and user-level) differentially private algorithms for graph problems under continual
    observation, i.e., differentially private dynamic graph algorithms. We present
    event-level private algorithms for partially dynamic counting-based problems such
    as triangle count that improve the additive error by a polynomial factor (in the
    length T of the update sequence) on the state of the art, resulting in the first
    algorithms with additive error polylogarithmic in T.\r\nWe also give ε-differentially
    private and partially dynamic algorithms for minimum spanning tree, minimum cut,
    densest subgraph, and maximum matching. The additive error of our improved MST
    algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which,
    as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we
    present a partially-dynamic algorithm with multiplicative error (1+β) for any
    constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show
    that the additive error for a broad class of dynamic graph algorithms with user-level
    privacy must be linear in the value of the output solution’s range.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Hendrik
      foaf_name: Fichtenberger, Hendrik
      foaf_surname: Fichtenberger
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Wolfgang
      foaf_name: Ost, Wolfgang
      foaf_surname: Ost
  bibo_doi: 10.4230/LIPIcs.ESA.2021.42
  bibo_volume: 204
  dct_date: 2021^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959772044
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Differentially private algorithms for graphs under continual observation@
...