Professor of computer science at University of Copenhagen. Interested in random things & their application (especially to algorithms and privacy). rasmuspagh.net
Rasmus Pagh
Loading...
Great to see participants from all over the world! The contributed talks have been very high quality, ranging from using formal methods to verify DP implementations, to new ways of reasoning about approximation algorithms under continual observation, to privacy in distributed ML and analytics.
Great invited talks by @ahonkela.bsky.social and @grahamrc.bsky.social on the Data Privacy in Machine Learning workshop's first day. Looking forward to day 2 which will focus on unlearning!
The first paper co-authored with my student Sia Sejer is out! We show how to do continual observation of sketches (and other data structures) with only a constant-factor time overhead relative to the non-private versions.
(I just realized that in fact the first paper co-authored with Sia came out a few weeks back, but this paper was our first project together so it is first in this sense.)
Finally, we present two applications based on Private CountSketch: An improved range counting data structure, and private sketches for join size (aka. F2) estimation.
The idea is to simulate the distribution of the binary tree mechanism without generating all noise values. Only when accessing a sketch entry do we generate the noise, and with a suitable data structure of size O(log T) it turns out that this is possible in constant time!
The paper also contains a new analysis of the binary tree mechanism with Gaussian noise, which turns out to have a better utility-privacy trade-off than some later refinements such as the smooth binary mechanism.
The program for our upcoming Workshop on Differential Privacy and Unlearning is now up on p1dpml.github.io/workshops/wo...
Registration deadline is Sunday June 7.
