---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Laxman
      foaf_name: Dhulipala, Laxman
      foaf_surname: Dhulipala
  - 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: George Z.
      foaf_name: Li, George Z.
      foaf_surname: Li
  - foaf_Person:
      foaf_givenName: Quanquan C.
      foaf_name: Liu, Quanquan C.
      foaf_surname: Liu
  - foaf_Person:
      foaf_givenName: A. R.
      foaf_name: Sricharan, A. R.
      foaf_surname: Sricharan
  - foaf_Person:
      foaf_givenName: Leqi
      foaf_name: Zhu, Leqi
      foaf_surname: Zhu
      foaf_workInfoHomepage: http://www.librecat.org/personId=a2117c59-cee4-11ed-b9d0-874ecf0f8ac5
  bibo_doi: 10.4230/LIPIcs.ESA.2025.91
  bibo_volume: 351
  dct_date: 2025^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959773959
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Near-optimal differentially private graph algorithms via the Multidimensional
    AboveThreshold Mechanism@
...