Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Campbell, Jesse, Zhu, Chunjiang
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
por: Mao, Xiao
Publicado: (2023)

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

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
por: Dory, Michal, et al.
Publicado: (2022)

All-Pairs Shortest Paths with Few Weights per Node
por: Abboud, Amir, et al.
Publicado: (2025)

Differentially Private Learning of Exponential Distributions: Simple Algorithms and Tight Bounds
por: Mahpud, Bar, et al.
Publicado: (2025)

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
por: Dhulipala, Laxman, et al.
Publicado: (2025)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
por: Mu, Ta-Yu, et al.
Publicado: (2024)

All-Hops Shortest Paths
por: Williams, Virginia Vassilevska, et al.
Publicado: (2024)

A fast algorithm for All-Pairs-Shortest-Paths suitable for neural networks
por: Jing, Zeyu, et al.
Publicado: (2023)

Differentially Private Substring and Document Counting with Near-Optimal Error
por: Bernardini, Giulia, et al.
Publicado: (2024)

Near-Universally-Optimal Differentially Private Minimum Spanning Trees
por: Hladík, Richard, et al.
Publicado: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

Faster All-Pairs Optimal Electric Car Routing
por: Dorfman, Dani, et al.
Publicado: (2025)

Near Optimal Dual Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
por: Huang, Zengfeng, et al.
Publicado: (2025)

Simple and Optimal Sublinear Algorithms for Mean Estimation
por: Bertolotti, Beatrice, et al.
Publicado: (2024)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
por: Chen, Daoyuan, et al.
Publicado: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
por: Brewer, Bruce W., et al.
Publicado: (2025)

Faster Algorithms for Shortest Unique or Absent Substrings
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2026)

InfTDA: A Simple TopDown Mechanism for Hierarchical Differentially Private Counting Queries
por: Boninsegna, Fabrizio
Publicado: (2025)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
por: Dhawan, Abhishek
Publicado: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
por: Sulser, Aurelio L., et al.
Publicado: (2024)

Improved All-Pairs Approximate Shortest Paths in Congested Clique
por: Bui, Hong Duc, et al.
Publicado: (2024)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
por: Bernstein, Aaron, et al.
Publicado: (2022)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
por: Yan, Shuyi
Publicado: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
por: He, Jialin, et al.
Publicado: (2025)

Near-Optimal Generalized Private Testing
por: Chaturvedi, Anamay, et al.
Publicado: (2026)

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

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
por: Ashvinkumar, Vikrant, et al.
Publicado: (2024)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
por: Choudhary, Keerti, et al.
Publicado: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
por: Haeupler, Bernhard, et al.
Publicado: (2025)

Near-Optimal Differentially Private k-Core Decomposition
por: Dhulipala, Laxman, et al.
Publicado: (2023)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
por: Gorbachev, Egor, et al.
Publicado: (2024)

Nearly-Optimal Private Selection via Gaussian Mechanism
por: Leeman, Ethan, et al.
Publicado: (2025)

On Differentially Private Linear Algebra
por: Kaplan, Haim, et al.
Publicado: (2024)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
por: Atalig, Sunny, et al.
Publicado: (2024)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
por: Yamano, Ryosuke, et al.
Publicado: (2026)

Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
por: Asi, Hilal, et al.
Publicado: (2024)