BARC talk by Tamalika Mukherjee

Friday, January 30, 2026, 10-11, Tamalika Mukherjee, Research Group Leader at the Max Planck Institute for Security and Privacy, will give a talk on "Differentially Private Shortest Distances in the Continual Release Model".

Abstract

In this talk, we initialize the study of all-pairs shortest distances within the continual release streaming model under differential privacy (DP). We consider a setting with a fixed graph topology and private, time-varying edge weights. We first establish a baseline pure DP mechanism for answering L shortest distance queries per timestep over a time horizon T. This mechanism achieves a worst-case error of $O(\sqrt(LT)/\epsilon)$ (omitting logarithmic factors), a result we prove is tight for the single-pair case (L=1) via a matching lower bound of $\Omega(\sqrt(T/\epsilon))$.

To improve these guarantees for structured graphs, we introduce the notion of a summary set for a collection of paths P. We prove that the existence of a (k,d)-summary set S—where k represents the maximum number of paths in S needed to compose any path in P, and d is the maximum edge frequency in S—yields an pure DP mechanism with worst-case error $O((kd*log|S| / \epsilon) * log^2 T)$.

We further extend these results to approximate DP and demonstrate their utility on specific topologies. For instance, we show that paths in cycles admit summary sets that yield tighter polylogarithmic error guarantees.

BIO

Tamalika Mukherjee is a research Group Leader at the Max Planck Institute for Security and Privacy. She completed her Ph.D. at Purdue University, where she was awarded the Bilsland Dissertation Fellowship. After the Ph.D. she was Postdoctoral Research Scientist at Columbia University. Her current research explores the intersection of data privacy and theoretical computer science and its impact.

Host

Rasmus Pagh