Rasmus Pagh
@rasmuspagh.net
Professor of computer science at University of Copenhagen. Interested in random things & their application (especially to algorithms and privacy). rasmuspagh.net
Over the past year, I've had the honor to work with the European Commission to help them understand Google's (terrible) approach to sharing anonymised search data with competitors under the Digital Markets Act, and design an alternative solution that preserves more utility. [1/3]
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.
Differential Privacy Papers@dppapers.bsky.social · 2mo agoA Fast Gaussian Mechanism under Continual Observation, with Applications Rasmus Pagh, Sia Sejer http://arxiv.org/abs/2606.11760
![A Fast Gaussian Mechanism under Continual Observation, with Applications
Rasmus Pagh, Sia Sejer
http://arxiv.org/abs/2606.11760
We consider the problem of privately releasing a $k$-dimensional vector under updates: Starting with a zero vector, at times $t_1, t_2,\dots$ the vector is updated by adding $x^{(1)}, x^{(2)},\dots$, respectively. For positive integers $T$, $k$ we model the updates as a data set $\{(t_i, x^{(i)})\}_i$, where $t_i \in [T]$ and $x^{(i)} \in B_k$ (the $k$-dimensional unit ball). Two such data sets are said to be neighboring if their symmetric difference has size at most $1$. The continual release consists of the sum $A^{(t)} = \sum_{i \; : \; t_i \leq t} x^{(i)}$ for each time step $t=1,\dots,T$. Classical continual release techniques allow us to release an approximation of $A^{(1)},\dots,A^{(T)}$ with additive noise of magnitude $\text{polylog}(T)$, computed in time $O(kT)$, even in the on-line, adaptive case where data is continually revealed for the current time step.
Motivated by private sketching techniques, we consider the setting where only a \emph{subset} of entries in $A^{(t)}$ need to be released at time step $t$. Our new result is that it is possible to sample any desired entry in a given noise vector in \emph{constant time} while reproducing exactly the distribution of the binary tree mechanism with Gaussian noise. The improvement on the known time bound of $O(\log T)$ comes from a new data structure that allows us to sample a new noise value with the correct correlations in constant time using Brownian bridges. We present two data management applications, of independent interest, that use our technique in conjunction with differentially private CountSketches: 1) A dynamic data structure for orthogonal range counting queries with a better privacy/accuracy/space trade-off than previous data structures, and 2) Join size estimation, where in addition we show improved high-probability bounds.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:bvdt4psvley2chbqednjkkw2/bafkreifu2lq2v3eytu7y6uxa6p46uddqv7xjmmcjbrcosdf2gnizgrhoai)
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!
Rasmus Pagh@rasmuspagh.net · 3mo agoJoin us June 11-12 for a workshop on Differential Privacy and Unlearning in Machine Learning at University of Copenhagen! The workshop will feature tutorials, three great invited speakers (@grahamrc.bsky.social, @ahonkela.bsky.social and @koloskova.bsky.social), as well as contributed talks.
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.
Differential Privacy and Unlearning in Machine Learning | Data Privacy in Machine Learning
p1dpml.github.io
Rasmus Pagh@rasmuspagh.net · 3mo agoJoin us June 11-12 for a workshop on Differential Privacy and Unlearning in Machine Learning at University of Copenhagen! The workshop will feature tutorials, three great invited speakers (@grahamrc.bsky.social, @ahonkela.bsky.social and @koloskova.bsky.social), as well as contributed talks.
Join us June 11-12 for a workshop on Differential Privacy and Unlearning in Machine Learning at University of Copenhagen! The workshop will feature tutorials, three great invited speakers (@grahamrc.bsky.social, @ahonkela.bsky.social and @koloskova.bsky.social), as well as contributed talks.
Last year Calmon, Du, Dwork, and Finley presented a remarkable result: If x is released with the Laplace noise, giving a noisy value x*, it is possible to estimate f(x) in an unbiased way for any f that is twice differentiable and does not have too high growth rate. drops.dagstuhl.de/entities/doc...
Debiasing Functions of Private Statistics in Postprocessing
drops.dagstuhl.de
This is such a fun idea: An LLM trained only on data from before 1930. You can try it out here: talkie-lm.com/chat
The privacy bug is spreading! Good colleagues from Technical University of Denmark and University of Southern Denmark featured in SIGMOD Record with a very nice paper on differentially private string data structures. dl.acm.org/doi/10.1145/...
A Differentially Private Data Structure for Substring and Document Counting | ACM SIGMOD Record
For databases consisting of many text documents, one of the most fundamental data analysis tasks is counting (i) how often a pattern appears as a substring in the database (substring counting) and (ii...
dl.acm.org
Congratulations to BARC alumnus Vincent Cohen-Addad and to @gautamkamath.com, very well deserved!
European Association for Theoretical Computer Science@eatcs.bsky.social · 3mo agoThe 2026 Presburger Award for Young Scientists goes to Vincent Cohen-Addad and @gautamkamath.com 🥳🎉 You can read the laudatio here:
Back in 2022 Niv Dayan was spending a few months with me at University of Copenhagen and asked some good questions about possibilities for adjusting the size of (hashing based) sketches. Ioana Bercea and Jakub Tetek joined the discussions, but we did not quite get interesting results.
It is now possible to submit comments on the European Commission's proposed rules for sharing Google search query data under the DMA: ec.europa.eu/eusurvey/run... I worry that the anonymization approach suggested has weak privacy and questionable data utility. 1/5
DMA.100209 - Consultation on the proposed measures for Google Search data sharing under Article 6(11) of the DMA
ec.europa.eu
Henna Virkkunen@hennavirkkunen.wsocial.eu · 4mo agoThis would enable third-party online search engines, or “data beneficiaries” to optimise their services and effectively contest Google Search’s position. To ensure that these proposed measures are effective, we invite interested parties to comment through a public consultation.
4색 정리 새로운 증명이 arXiv에 올라왔습니다. New proof of the four color theorem by Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup arxiv.org/abs/2603.24880
The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
We give a near-linear time 4-coloring algorithm for planar graphs, improving on the previous quadratic time algorithm by Robertson et al. from 1996. Such an algorithm cannot be achieved by the known p...
arxiv.org
The 1st European Workshop on the Theory of Differential Privacy (eurotdp.pages.ista.ac.at) will open for submissions today! We expect to be open for submissions until end of April, but there is limited capacity so we may need to stop accepting submissions earlier. Send a 4-page abstract, like TPDP.
EuroTDP
eurotdp.pages.ista.ac.at
Simple tabulation hashing, originally proposed by Zobrist, is only 3-wise independent yet Pătrașcu and Thorup (JACM 2012) showed that it has powerful theoretical properties. Today it occurred to me that it would be fitting to refer to Zobrist, Pătrașcu and Thorup as the "3-wise men"
Really looking forward to our Dagstuhl seminar on data sharing and differential privacy early next year! www.dagstuhl.de/27032
Dagstuhl Seminar 27032: Data Sharing and Differential Privacy
dagstuhl.de
New: Also post-doc positions at ITU, application deadline March 15, affiliated with BARC and/or AHA. Link: candidate.hr-manager.net/ApplicationI... The PhD position previously announced has deadline March 10. Join us in Copenhagen!
Talentech - Postdoc position for Algebraic Complexity Theory and Theoretical Computer Science at the IT University of Copenhagen
candidate.hr-manager.net
Rasmus Pagh@rasmuspagh.net · 6mo agoMy awesome BARC colleague @nutanlimaye.bsky.social is starting a major research project in algebraic complexity. Anyone interested in joining as a PhD student should check out the call (deadline March 1). barc.ku.dk/news/profess...
My awesome BARC colleague @nutanlimaye.bsky.social is starting a major research project in algebraic complexity. Anyone interested in joining as a PhD student should check out the call (deadline March 1). barc.ku.dk/news/profess...
Professor Nutan Limaye receives DKK 12.8 million for research on algebraic complexity
The project explores fundamental limits of efficient computation, linking algebraic methods with randomness and parallelism to advance complexity theory.
barc.ku.dk
Do you have recent work on differential privacy? Submit it to TPDP 2026 in Boston, whose deadline is in ~2 weeks. TPDP is a lightly reviewed workshop, whose main purpose is getting researchers in DP together in one place. Dual submissions allowed (and encouraged!).
According to Google Search, my primary contribution to human knowledge is the collection of database exams (with answers) that I developed in 2003-2012.
The recommendations of this paper, published in Science yesterday, should be required reading for policymakers across the world. We need to make democratic debate more robust. arxiv.org/pdf/2506.06299
arxiv.org
Between 1939 and 1969 the fastest speed at which a human could move was subject to a dramatic growth of around 17% per year due to technological advances. If this trend had continued to this day we would now be traveling at near light speed.
ELLIS Institute Finland @ellisinstitute.fi has an open call for postdocs (DL 9 Feb) www.ellisinstitute.fi/postdoc-recr... There are 45 PIs with different topics to choose from, including privacy in machine learning with me!
Postdoc positions at ELLIS Institute Finland | ELLIS Institute Finland
Call for postdoctoral researchers in artificial intelligence and machine learning
ellisinstitute.fi
Today I realized that the power mean inequality extends AM–GM–HM to P_r ≥ A ≥ G ≥ H. Unexpected perk: my surname is now a theorem.
Consider signing this petition regarding restoring free access to the ACM digital library: www.ipetitions.com/petition/res...
Petition Restore Fully Free and Open Access to the ACM Digital Library
Restore Fully Free and Open Access to the ACM Digital Library
ipetitions.com
The deadline for BARC's annual call for PhD positions is soon (January 10)!
Rasmus Pagh@rasmuspagh.net · 8mo agoWant to join the ambitious, creative, collaborative, and fun environment at BARC? Our annual call for PhD or integrated MSc + PhD fellowship in Algorithms has been posted! Apply by January 10. employment.ku.dk/phd/?show=15...
Starting in the fall (Gemini 2.5 pro launched experimentally at the end of March) LLMs that were useful for math launched. I didn't have much luck using them within their web interface, but I found them to be extremely useful within coding agent harnesses like Windsurf.
Postdoc and PhD positions in combinatorial optimization and/or TCS at Lund University. Application deadline January 16. Postdoc position info at jakobnordstrom.se/openings/Pos... and PhD info at jakobnordstrom.se/openings/PhD....
Jakob Nordström: Postdoc position in combinatorial optimization and/or theoretical computer science
jakobnordstrom.se
Want to join the ambitious, creative, collaborative, and fun environment at BARC? Our annual call for PhD or integrated MSc + PhD fellowship in Algorithms has been posted! Apply by January 10. employment.ku.dk/phd/?show=15...
BARC – University of Copenhagen
barc.ku.dk
STOC'26 will have an experimental program: Automated pre-submission feedback. It is opt-in, providing authors with "pre-submission feedback on their papers generated by an advanced LLM-based tool based on Google’s Gemini model that has been optimized for mathematical rigor". Deadline Nov 1, 5pm EST
STOC 2026 Experimental Program: Automated Pre-Submission Feedback
acm-stoc.org
As the STOC deadline is approaching it may be of interest to authors that the ACM policy on authorship (www.acm.org/publications...) applies to submissions. Unfortunately this does not yet seem to be reflected in the CFP. In particular, the policy describes how use of generative AI must be declared: