Buchumschlag

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Campbell, Jesse, Zhu, Chunjiang
Format:	Preprint
Veröffentlicht:	2024
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

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
von: Das, Debarati, et al.
Veröffentlicht: (2026)

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
von: Dinitz, Michael, et al.
Veröffentlicht: (2025)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
von: Mao, Xiao
Veröffentlicht: (2023)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

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

All-Pairs Shortest Paths with Few Weights per Node
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

Differentially Private Learning of Exponential Distributions: Simple Algorithms and Tight Bounds
von: Mahpud, Bar, et al.
Veröffentlicht: (2025)

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
von: Dhulipala, Laxman, et al.
Veröffentlicht: (2025)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

All-Hops Shortest Paths
von: Williams, Virginia Vassilevska, et al.
Veröffentlicht: (2024)

A fast algorithm for All-Pairs-Shortest-Paths suitable for neural networks
von: Jing, Zeyu, et al.
Veröffentlicht: (2023)

Differentially Private Substring and Document Counting with Near-Optimal Error
von: Bernardini, Giulia, et al.
Veröffentlicht: (2024)

Near-Universally-Optimal Differentially Private Minimum Spanning Trees
von: Hladík, Richard, et al.
Veröffentlicht: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
von: Dey, Dipan, et al.
Veröffentlicht: (2024)

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

Near Optimal Dual Fault Tolerant Distance Oracle
von: Dey, Dipan, et al.
Veröffentlicht: (2024)

Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
von: Huang, Zengfeng, et al.
Veröffentlicht: (2025)

Simple and Optimal Sublinear Algorithms for Mean Estimation
von: Bertolotti, Beatrice, et al.
Veröffentlicht: (2024)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
von: Chen, Daoyuan, et al.
Veröffentlicht: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2025)

Faster Algorithms for Shortest Unique or Absent Substrings
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2026)

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

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
von: Sulser, Aurelio L., et al.
Veröffentlicht: (2024)

Improved All-Pairs Approximate Shortest Paths in Congested Clique
von: Bui, Hong Duc, et al.
Veröffentlicht: (2024)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2022)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
von: Yan, Shuyi
Veröffentlicht: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
von: He, Jialin, et al.
Veröffentlicht: (2025)

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

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2020)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
von: Choudhary, Keerti, et al.
Veröffentlicht: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Near-Optimal Differentially Private k-Core Decomposition
von: Dhulipala, Laxman, et al.
Veröffentlicht: (2023)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
von: Gorbachev, Egor, et al.
Veröffentlicht: (2024)

Nearly-Optimal Private Selection via Gaussian Mechanism
von: Leeman, Ethan, et al.
Veröffentlicht: (2025)

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

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
von: Atalig, Sunny, et al.
Veröffentlicht: (2024)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
von: Yamano, Ryosuke, et al.
Veröffentlicht: (2026)

Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
von: Asi, Hilal, et al.
Veröffentlicht: (2024)