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

Jesse Campbell, Chunjiang Zhu

The all-pairs shortest distances (APSD) with differential privacy (DP) problem takes as input an undirected, weighted graph $G=(V,E,\mathbf{w})$ and outputs a private estimate o…