---
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'
...