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
An IBLT (Goodrich & Mitzenmacher 2011) is an integer vector encoding a multiset in a linear way: IBLT(A)+IBLT(B)=IBLT(A∪B). Subtracting, IBLT(A)-IBLT(B) is an IBLT where the multiplicity of x is the difference between its multiplicity in A and its multiplicity in B (negative multiplicities are ok).
September 16, 2026 at 7:52 PM
An IBLT (Goodrich & Mitzenmacher 2011) is an integer vector encoding a multiset in a linear way: IBLT(A)+IBLT(B)=IBLT(A∪B). Subtracting, IBLT(A)-IBLT(B) is an IBLT where the multiplicity of x is the difference between its multiplicity in A and its multiplicity in B (negative multiplicities are ok).
Horner's rule is one of the first nontrivial algorithms many students see: Rather than using a quadratic number of multiplications to evaluate a degree-n polynomial term-by-term, it suffices to use n-1 multiplications. This optimization is important, e.g., for evaluating polynomial hash functions.
September 14, 2026 at 10:48 AM
Horner's rule is one of the first nontrivial algorithms many students see: Rather than using a quadratic number of multiplications to evaluate a degree-n polynomial term-by-term, it suffices to use n-1 multiplications. This optimization is important, e.g., for evaluating polynomial hash functions.
Reposted by Rasmus Pagh
Registration for the PPML workshop in Aarhus November 2-4 is now open. The deadline for talk submissions is also this week (September 10).
Feel free to reshare!
p1dpml.github.io/workshops/wo...
Feel free to reshare!
p1dpml.github.io/workshops/wo...
September 7, 2026 at 7:55 AM
Registration for the PPML workshop in Aarhus November 2-4 is now open. The deadline for talk submissions is also this week (September 10).
Feel free to reshare!
p1dpml.github.io/workshops/wo...
Feel free to reshare!
p1dpml.github.io/workshops/wo...
Upcoming workshop in Aarhus on Privacy-preserving Machine Learning and Privacy in Distributed Settings in early November. Registration: p1dpml.github.io/workshops/wo...
This is a great opportunity to learn about new developments in the privacy/cryptography intersection!
This is a great opportunity to learn about new developments in the privacy/cryptography intersection!
Workshop 2 | Data Privacy in Machine Learning
p1dpml.github.io
September 7, 2026 at 7:53 AM
Upcoming workshop in Aarhus on Privacy-preserving Machine Learning and Privacy in Distributed Settings in early November. Registration: p1dpml.github.io/workshops/wo...
This is a great opportunity to learn about new developments in the privacy/cryptography intersection!
This is a great opportunity to learn about new developments in the privacy/cryptography intersection!
Congratulations to Susanna Rezende, Or Zamir, and other ERC Starting Grant recipients!
📣 Good news! 📣
Results of the ERC 2026 Starting Grant call are out!
Funding worth a total of €705 million will go to 421 early-career researchers across Europe.
Discover who, what and where 👉 link.europa.eu/9M3MmN
🧪 #ERCStG #FrontierResearch #HorizonEurope
🇪🇺 @scienceinnovation.ec.europa.eu
Results of the ERC 2026 Starting Grant call are out!
Funding worth a total of €705 million will go to 421 early-career researchers across Europe.
Discover who, what and where 👉 link.europa.eu/9M3MmN
🧪 #ERCStG #FrontierResearch #HorizonEurope
🇪🇺 @scienceinnovation.ec.europa.eu
September 3, 2026 at 1:28 PM
Congratulations to Susanna Rezende, Or Zamir, and other ERC Starting Grant recipients!
Reposted by Rasmus Pagh
Recordings from FORC 2026 are now available! Please check them out.
Also, subscribe to FORC's new YouTube channel while you're at it!
www.youtube.com/playlist?lis...
Also, subscribe to FORC's new YouTube channel while you're at it!
www.youtube.com/playlist?lis...
FORC 2026 - YouTube
Talk recordings from FORC 2026
www.youtube.com
August 17, 2026 at 3:34 PM
Recordings from FORC 2026 are now available! Please check them out.
Also, subscribe to FORC's new YouTube channel while you're at it!
www.youtube.com/playlist?lis...
Also, subscribe to FORC's new YouTube channel while you're at it!
www.youtube.com/playlist?lis...
Reposted by Rasmus Pagh
Join us in Aarhus, Nov 2–4, for the Workshop on Privacy-Preserving Machine Learning and Privacy in Distributed Settings!
We invite talks on relevant topics including federated learning, differential privacy, MPC, attacks, and more.
Deadline: Sept 10
p1dpml.github.io/workshops/wo...
We invite talks on relevant topics including federated learning, differential privacy, MPC, attacks, and more.
Deadline: Sept 10
p1dpml.github.io/workshops/wo...
Workshop 2 | Data Privacy in Machine Learning
p1dpml.github.io
August 12, 2026 at 12:25 PM
Join us in Aarhus, Nov 2–4, for the Workshop on Privacy-Preserving Machine Learning and Privacy in Distributed Settings!
We invite talks on relevant topics including federated learning, differential privacy, MPC, attacks, and more.
Deadline: Sept 10
p1dpml.github.io/workshops/wo...
We invite talks on relevant topics including federated learning, differential privacy, MPC, attacks, and more.
Deadline: Sept 10
p1dpml.github.io/workshops/wo...
We are excited to invite submissions for our upcoming Workshop on Privacy-preserving Machine Learning and Privacy in Distributed Settings! The workshop will be held November 2-4 at Aarhus University in Aarhus, Denmark and is part of the @aicentre.dk Program on Data Privacy in Machine Learning.
Workshop 2 | Data Privacy in Machine Learning
p1dpml.github.io
August 12, 2026 at 11:52 AM
We are excited to invite submissions for our upcoming Workshop on Privacy-preserving Machine Learning and Privacy in Distributed Settings! The workshop will be held November 2-4 at Aarhus University in Aarhus, Denmark and is part of the @aicentre.dk Program on Data Privacy in Machine Learning.
Reposted by Rasmus Pagh
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]
July 16, 2026 at 1:13 PM
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.
A Fast Gaussian Mechanism under Continual Observation, with Applications
Rasmus Pagh, Sia Sejer
http://arxiv.org/abs/2606.11760
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)
June 12, 2026 at 6:56 AM
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.
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!
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.
June 12, 2026 at 6:46 AM
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 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.
Registration deadline is Sunday June 7.
June 1, 2026 at 8:30 PM
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.
Registration deadline is Sunday June 7.
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.
May 11, 2026 at 1:42 PM
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
May 8, 2026 at 7:46 AM
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...
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
April 29, 2026 at 2:05 PM
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
April 28, 2026 at 1:41 PM
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/...
Congratulations to BARC alumnus Vincent Cohen-Addad and to @gautamkamath.com, very well deserved!
The 2026 Presburger Award for Young Scientists goes to Vincent Cohen-Addad and @gautamkamath.com 🥳🎉
You can read the laudatio here:
You can read the laudatio here:
Presburger Award 2026 – Laudatio
European Association for Theoretical Computer Science
www.eatcs.org
April 27, 2026 at 11:22 AM
Congratulations to BARC alumnus Vincent Cohen-Addad and to @gautamkamath.com, very well deserved!
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.
April 27, 2026 at 6:45 AM
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
I worry that the anonymization approach suggested has weak privacy and questionable data utility. 1/5
April 22, 2026 at 9:13 AM
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
I worry that the anonymization approach suggested has weak privacy and questionable data utility. 1/5
Reposted by Rasmus Pagh
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
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
March 27, 2026 at 12:39 PM
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
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 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
April 1, 2026 at 6:12 AM
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.
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"
March 31, 2026 at 1:56 PM
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
www.dagstuhl.de
March 16, 2026 at 2:59 PM
Really looking forward to our Dagstuhl seminar on data sharing and differential privacy early next year! www.dagstuhl.de/27032
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!
The PhD position previously announced has deadline March 10. Join us in Copenhagen!
February 27, 2026 at 9:30 PM
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!
The PhD position previously announced has deadline March 10. Join us in Copenhagen!
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...
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
February 10, 2026 at 8:59 AM
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...
barc.ku.dk/news/profess...