Buchumschlag

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dinitz, Michael, Fan, Chenglin, Liu, Jingcheng, Upadhyay, Jalaj, Zou, Zongrui
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
von: Chandra, Rishi, et al.
Veröffentlicht: (2024)

Almost linear time differentially private release of synthetic graphs
von: Liu, Jingcheng, et al.
Veröffentlicht: (2024)

Improved Differentially Private Continual Observation Using Group Algebra
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Almost Tight Error Bounds on Differentially Private Continual Counting
von: Henzinger, Monika, et al.
Veröffentlicht: (2022)

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
von: Fichtenberger, Hendrik, et al.
Veröffentlicht: (2022)

Near-Optimal Generalized Private Testing
von: Chaturvedi, Anamay, et al.
Veröffentlicht: (2026)

Binned Group Algebra Factorization for Differentially Private Continual Counting
von: Henzinger, Monika, et al.
Veröffentlicht: (2025)

Almost Tight Bounds for Differentially Private Densest Subgraph
von: Dinitz, Michael, et al.
Veröffentlicht: (2023)

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances
von: Campbell, Jesse, et al.
Veröffentlicht: (2024)

Differentially Private Matchings
von: Dinitz, Michael, et al.
Veröffentlicht: (2025)

Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting
von: Henzinger, Monika, et al.
Veröffentlicht: (2025)

The Price of Privacy For Approximating Max-CSP
von: Dharangutte, Prathamesh, et al.
Veröffentlicht: (2026)

Tree Search With Predictions
von: Dinitz, Michael, et al.
Veröffentlicht: (2026)

Approximation Algorithms for Optimal Hopsets
von: Dinitz, Michael, et al.
Veröffentlicht: (2025)

Controlling tail risk in two-slope ski rental
von: Cui, Qiming, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
von: Fan, Chenglin, et al.
Veröffentlicht: (2025)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
von: Lee, Dahoon, et al.
Veröffentlicht: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
von: Dory, Michal, et al.
Veröffentlicht: (2022)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
von: Dinitz, Michael, et al.
Veröffentlicht: (2025)

Ski Rental with Distributional Predictions of Unknown Quality
von: Cui, Qiming, et al.
Veröffentlicht: (2026)

On the Price of Differential Privacy for Hierarchical Clustering
von: Deng, Chengyuan, et al.
Veröffentlicht: (2025)

Binary Search with Distributional Predictions
von: Dinitz, Michael, et al.
Veröffentlicht: (2024)

The Discrepancy of Shortest Paths
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Differentially Private High-Dimensional Approximate Range Counting, Revisited
von: Aumüller, Martin, et al.
Veröffentlicht: (2024)

Concurrent Composition for Differentially Private Continual Mechanisms
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Designing Approximate Binary Trees for Trees
von: Kellerhals, Leon, et al.
Veröffentlicht: (2026)

The Steiner Shortest Path Tree Problem
von: Asher, Omer, et al.
Veröffentlicht: (2025)

InfTDA: A Simple TopDown Mechanism for Hierarchical Differentially Private Counting Queries
von: Boninsegna, Fabrizio
Veröffentlicht: (2025)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

On Differentially Private Linear Algebra
von: Kaplan, Haim, et al.
Veröffentlicht: (2024)

Continual Counting with Gradual Privacy Expiration
von: Andersson, Joel Daniel, et al.
Veröffentlicht: (2024)

Differentially Private Quantiles with Smaller Error
von: Imola, Jacob, et al.
Veröffentlicht: (2025)

On Differentially Private String Distances
von: Hu, Jerry Yao-Chieh, et al.
Veröffentlicht: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2023)

Faster All-Pairs Optimal Electric Car Routing
von: Dorfman, Dani, et al.
Veröffentlicht: (2025)

A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
von: Dempsey, Jordan, et al.
Veröffentlicht: (2024)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
von: Kaul, Matthias, et al.
Veröffentlicht: (2025)

Differentially Private Selection using Smooth Sensitivity
von: Yamamoto, Akito, et al.
Veröffentlicht: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
von: Dumitrescu, Adrian
Veröffentlicht: (2021)