Please note: This seminar will take place in DC 1304 and online.

Jacob Imola, Postdoctoral Scholar
David R. Cheriton School of Computer Science

The edge-weight model of differential privacy is a natural privacy notion for weighted graphs where the weights are a result of sensitive user interactions (e.g. road or network traffic). In this talk, I will illustrate new lower bounds for two natural combinatorial optimization problems under edge-weight DP: minimum spanning trees, and hierarchical clustering. These lower bounds come via reconstruction attacks, where an algorithm with low error is used to reconstruct a private dataset that has been cleverly encoded into the edge weights, ruling out privacy.

I will show two flavors of lower bounds: the first exhibits a worst-case graph and encoding strategy where the MST error is provably higher than previously known bounds and is tight with the best-known upper bound. The second flavor exhibits a large class of sparse graphs where the error asymptotically matches that of the worst-case graph up to log factors for both the MST and HC problems. These results are further evidence of the amazing versatility of reconstruction attacks in proving privacy impossibility and leave several interesting follow-up questions for future work.

To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.