# Open Problem: Private All-Pairs Distances

Background: Suppose we are interested in computing the distance between two vertices in a graph. Under edge or node differential privacy, this problem is not promising because the removal of a single edge can make distances change from 1 to $$n − 1$$ or can even disconnect the graph. However, a different setting that makes sense to consider is that of a weighted graph $$(G, w)$$ whose topology $$G = (V, E)$$ is publicly known but edge weight function $$w : E \to \mathbb{R}^+$$ must be kept private. (For instance, consider transit times on a road network. The topology of the road network may be publicly available as a map, but the edge weights corresponding to transit times may be based on private GPS locations of individual cars.)

# The Pitfalls of Average-Case Differential Privacy

Differential privacy protects against extremely strong adversaries—even ones who know the entire dataset except for one bit of information about one individual. Since its inception, people have considered ways to relax the definition to assume a more realistic adversary. A natural way to do so is to incorporate some distributional assumptions. That is, rather than considering a worst-case dataset, assume the dataset is drawn from some distribution and provide some form of “average-case” or “Bayesian” privacy guarantee with respect to this distribution. This is especially tempting as it is common for statistical analysis to work under distributional assumptions.

# Conference Digest - STOC 2020

STOC 2020 was recently held online, as one of the first major theory conferences during the COVID-19 era. It featured four papers on differential privacy, which we list and link below. Each one is accompanied by a video from the conference, as well as a longer video if available. Please let us know if we missed any papers on differential privacy, either in the comments below or by email.