---
OA_place: publisher
OA_type: gold
_id: '20533'
abstract:
- lang: eng
  text: We give an introduction into differential privacy in the dynamic setting,
    called the continual observation setting.
alternative_title:
- LIPIcs
article_number: '2'
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Roodabeh
  full_name: Safavi Hemami, Roodabeh
  id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
  last_name: Safavi Hemami
citation:
  ama: 'Henzinger M, Safavi Hemami R. Securing dynamic data: A primer on differentially
    private data structures. In: <i>33rd Annual European Symposium on Algorithms</i>.
    Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2025.2">10.4230/LIPIcs.ESA.2025.2</a>'
  apa: 'Henzinger, M., &#38; Safavi Hemami, R. (2025). Securing dynamic data: A primer
    on differentially private data structures. In <i>33rd Annual European Symposium
    on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ESA.2025.2">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>'
  chicago: 'Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data:
    A Primer on Differentially Private Data Structures.” In <i>33rd Annual European
    Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2025. <a href="https://doi.org/10.4230/LIPIcs.ESA.2025.2">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>.'
  ieee: 'M. Henzinger and R. Safavi Hemami, “Securing dynamic data: A primer on differentially
    private data structures,” in <i>33rd Annual European Symposium on Algorithms</i>,
    Warsaw, Poland, 2025, vol. 351.'
  ista: 'Henzinger M, Safavi Hemami R. 2025. Securing dynamic data: A primer on differentially
    private data structures. 33rd Annual European Symposium on Algorithms. ESA: European
    Symposium on Algorithms, LIPIcs, vol. 351, 2.'
  mla: 'Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer
    on Differentially Private Data Structures.” <i>33rd Annual European Symposium
    on Algorithms</i>, vol. 351, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2025, doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2025.2">10.4230/LIPIcs.ESA.2025.2</a>.'
  short: M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
  end_date: 2025-09-17
  location: Warsaw, Poland
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2025-09-15
corr_author: '1'
date_created: 2025-10-26T23:01:34Z
date_published: 2025-10-01T00:00:00Z
date_updated: 2025-10-27T08:00:13Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2025.2
file:
- access_level: open_access
  checksum: 094e0466d90664fbea397b469a60acbb
  content_type: application/pdf
  creator: dernst
  date_created: 2025-10-27T07:57:00Z
  date_updated: 2025-10-27T07:57:00Z
  file_id: '20541'
  file_name: 2025_LIPIcs.ESA_Henzinger.pdf
  file_size: 770227
  relation: main_file
  success: 1
file_date_updated: 2025-10-27T07:57:00Z
has_accepted_license: '1'
intvolume: '       351'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '10'
oa: 1
oa_version: Published Version
publication: 33rd Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959773959'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Securing dynamic data: A primer on differentially private data structures'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 351
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20534'
abstract:
- lang: eng
  text: "A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves
    all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible
    data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier
    upon request at any point during the sequence of updates. We employ simple dynamic
    forest data structures to achieve a fast from-scratch construction of the sparsifier
    at query time. Based on the strength of the adversary and desired type of time
    bounds, the data structure comes with different guarantees. Specifically, let
    G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our
    data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case
    time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that
    has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees
    hold against an adaptive adversary. Alternatively, the update and query times
    can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees
    are sufficient, or if the adversary is oblivious. Throughout the paper, we use
    Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1))
    factors.\r\nWe discuss two applications of our new data structure. First, it can
    be used to efficiently report a cactus representation of all minimum cuts of a
    fully dynamic simple graph. Building this cactus for the NMC sparsifier instead
    of the original graph allows for a construction time that is sublinear in the
    number of edges. Against an adaptive adversary, we can with high probability output
    the cactus representation in worst-case Ô(n) time. Second, our data structure
    allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected
    simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier.
    Specifically, we can compute with high probability the maximal k-edge-connected
    subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This
    improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to
    the case of fully dynamic graphs."
acknowledgement: 'Monika Henzinger and Evangelos Kosinas: This project has received
  funding from the European Research Council (ERC) under the European Union’s Horizon
  2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian
  Science Fund (FWF) grant https://www.doi.org/10.55776/Z422 and grant https://www.doi.org/10.55776/I5982.
  Harald Räcke and Robin Münk: This project has received funding from the Deutsche
  Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858.'
article_number: '36'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Evangelos
  full_name: Kosinas, Evangelos
  id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949
  last_name: Kosinas
- first_name: Robin
  full_name: Münk, Robin
  last_name: Münk
- first_name: Harald
  full_name: Räcke, Harald
  last_name: Räcke
citation:
  ama: 'Henzinger M, Kosinas E, Münk R, Räcke H. Efficient contractions of dynamic
    graphs - with applications. In: <i>33rd Annual European Symposium on Algorithms</i>.
    Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2025.36">10.4230/LIPIcs.ESA.2025.36</a>'
  apa: 'Henzinger, M., Kosinas, E., Münk, R., &#38; Räcke, H. (2025). Efficient contractions
    of dynamic graphs - with applications. In <i>33rd Annual European Symposium on
    Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ESA.2025.36">https://doi.org/10.4230/LIPIcs.ESA.2025.36</a>'
  chicago: Henzinger, Monika, Evangelos Kosinas, Robin Münk, and Harald Räcke. “Efficient
    Contractions of Dynamic Graphs - with Applications.” In <i>33rd Annual European
    Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2025. <a href="https://doi.org/10.4230/LIPIcs.ESA.2025.36">https://doi.org/10.4230/LIPIcs.ESA.2025.36</a>.
  ieee: M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of
    dynamic graphs - with applications,” in <i>33rd Annual European Symposium on Algorithms</i>,
    Warsaw, Poland, 2025, vol. 351.
  ista: 'Henzinger M, Kosinas E, Münk R, Räcke H. 2025. Efficient contractions of
    dynamic graphs - with applications. 33rd Annual European Symposium on Algorithms.
    ESA: European Symposium on Algorithms vol. 351, 36.'
  mla: Henzinger, Monika, et al. “Efficient Contractions of Dynamic Graphs - with
    Applications.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351,
    36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2025.36">10.4230/LIPIcs.ESA.2025.36</a>.
  short: M. Henzinger, E. Kosinas, R. Münk, H. Räcke, in:, 33rd Annual European Symposium
    on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
  end_date: 2025-09-17
  location: Warsaw, Poland
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2025-09-15
corr_author: '1'
date_created: 2025-10-26T23:01:34Z
date_published: 2025-10-01T00:00:00Z
date_updated: 2025-10-27T08:05:46Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2025.36
ec_funded: 1
external_id:
  arxiv:
  - '2509.05157'
file:
- access_level: open_access
  checksum: d2daf9a467e96fb5e7084a8a85321776
  content_type: application/pdf
  creator: dernst
  date_created: 2025-10-27T08:03:36Z
  date_updated: 2025-10-27T08:03:36Z
  file_id: '20542'
  file_name: 2025_LIPIcs.ESA_HenzingerM.pdf
  file_size: 934846
  relation: main_file
  success: 1
file_date_updated: 2025-10-27T08:03:36Z
has_accepted_license: '1'
intvolume: '       351'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
  grant_number: Z00422
  name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
publication: 33rd Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959773959'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Efficient contractions of dynamic graphs - with applications
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 351
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20535'
abstract:
- lang: eng
  text: "Many differentially private and classical non-private graph algorithms rely
    crucially on determining whether some property of each vertex meets a threshold.
    For example, for the k-core decomposition problem, the classic peeling algorithm
    iteratively removes a vertex if its induced degree falls below a threshold. The
    sparse vector technique (SVT) is generally used to transform non-private threshold
    queries into private ones with only a small additive loss in accuracy. However,
    a naive application of SVT in the graph setting leads to an amplification of the
    error by a factor of n due to composition, as SVT is applied to every vertex.
    In this paper, we resolve this problem by formulating a novel generalized sparse
    vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism
    which generalizes SVT (applied to vectors with one dimension) to vectors with
    multiple dimensions. When applied to vectors with n dimensions, we solve a number
    of important graph problems with better bounds than previous work.\r\nSpecifically,
    we apply our MAT mechanism to obtain a set of improved bounds for a variety of
    problems including k-core decomposition, densest subgraph, low out-degree ordering,
    and vertex coloring. We give a tight local edge differentially private (LEDP)
    algorithm for k-core decomposition that results in an approximation with O(ε^{-1}
    log n) additive error and no multiplicative error in O(n) rounds. We also give
    a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in
    O(log² n) rounds for any constant η > 0. Both of these results are asymptotically
    tight against our new lower bound of Ω(log n) for any constant-factor approximation
    algorithm for k-core decomposition. Our new algorithms for k-core decomposition
    also directly lead to new algorithms for the related problems of densest subgraph
    and low out-degree ordering. Finally, we give novel LEDP differentially private
    defective coloring algorithms that use number of colors given in terms of the
    arboricity of the graph."
acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received
  funding from the European Research Council (ERC) under the European Union’s Horizon
  2020 research and innovation\r\nprogramme (MoDynStruct, No. 101019564) and the Austrian
  Science Fund (FWF) grant DOI\r\n10.55776/Z422 and grant DOI 10.55776/I5982. Laxman
  Dhulipala and George Z. Li: supported by NSF award number CNS-2317194. Quanquan
  C. Liu: supported by a Google Academic Research Award and by an NSF award number
  CCF-2453323."
alternative_title:
- LIPIcs
article_number: '91'
article_processing_charge: No
arxiv: 1
author:
- first_name: Laxman
  full_name: Dhulipala, Laxman
  last_name: Dhulipala
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: George Z.
  full_name: Li, George Z.
  last_name: Li
- first_name: Quanquan C.
  full_name: Liu, Quanquan C.
  last_name: Liu
- first_name: A. R.
  full_name: Sricharan, A. R.
  last_name: Sricharan
- first_name: Leqi
  full_name: Zhu, Leqi
  id: a2117c59-cee4-11ed-b9d0-874ecf0f8ac5
  last_name: Zhu
citation:
  ama: 'Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. Near-optimal
    differentially private graph algorithms via the Multidimensional AboveThreshold
    Mechanism. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2025.91">10.4230/LIPIcs.ESA.2025.91</a>'
  apa: 'Dhulipala, L., Henzinger, M., Li, G. Z., Liu, Q. C., Sricharan, A. R., &#38;
    Zhu, L. (2025). Near-optimal differentially private graph algorithms via the Multidimensional
    AboveThreshold Mechanism. In <i>33rd Annual European Symposium on Algorithms</i>
    (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.ESA.2025.91">https://doi.org/10.4230/LIPIcs.ESA.2025.91</a>'
  chicago: Dhulipala, Laxman, Monika Henzinger, George Z. Li, Quanquan C. Liu, A.
    R. Sricharan, and Leqi Zhu. “Near-Optimal Differentially Private Graph Algorithms
    via the Multidimensional AboveThreshold Mechanism.” In <i>33rd Annual European
    Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2025. <a href="https://doi.org/10.4230/LIPIcs.ESA.2025.91">https://doi.org/10.4230/LIPIcs.ESA.2025.91</a>.
  ieee: L. Dhulipala, M. Henzinger, G. Z. Li, Q. C. Liu, A. R. Sricharan, and L. Zhu,
    “Near-optimal differentially private graph algorithms via the Multidimensional
    AboveThreshold Mechanism,” in <i>33rd Annual European Symposium on Algorithms</i>,
    Warsaw, Poland, 2025, vol. 351.
  ista: 'Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. 2025. Near-optimal
    differentially private graph algorithms via the Multidimensional AboveThreshold
    Mechanism. 33rd Annual European Symposium on Algorithms. ESA: European Symposium
    on Algorithms, LIPIcs, vol. 351, 91.'
  mla: Dhulipala, Laxman, et al. “Near-Optimal Differentially Private Graph Algorithms
    via the Multidimensional AboveThreshold Mechanism.” <i>33rd Annual European Symposium
    on Algorithms</i>, vol. 351, 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2025, doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2025.91">10.4230/LIPIcs.ESA.2025.91</a>.
  short: L. Dhulipala, M. Henzinger, G.Z. Li, Q.C. Liu, A.R. Sricharan, L. Zhu, in:,
    33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2025.
conference:
  end_date: 2025-09-17
  location: Warsaw, Poland
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2025-09-15
corr_author: '1'
date_created: 2025-10-26T23:01:35Z
date_published: 2025-10-01T00:00:00Z
date_updated: 2025-10-27T07:02:06Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2025.91
ec_funded: 1
external_id:
  arxiv:
  - '2508.02182'
file:
- access_level: open_access
  checksum: 19146e935b5b6ad5d33c8d08280ad8e7
  content_type: application/pdf
  creator: dernst
  date_created: 2025-10-27T06:58:43Z
  date_updated: 2025-10-27T06:58:43Z
  file_id: '20539'
  file_name: 2025_LIPIcs.ESA_Dhulipala.pdf
  file_size: 870317
  relation: main_file
  success: 1
file_date_updated: 2025-10-27T06:58:43Z
has_accepted_license: '1'
intvolume: '       351'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
  grant_number: Z00422
  name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
publication: 33rd Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959773959'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Near-optimal differentially private graph algorithms via the Multidimensional
  AboveThreshold Mechanism
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 351
year: '2025'
...