Rasmus Pagh

Truly subquadratic time for 3SUM is a problem I have thought about on and off for many years. Now a breakthrough result has been announced by Josh Alman and Virginia Vassilevska Williams! arxiv.org/abs/2610.06783

The algorithms were first discovered at Anthropic by an internal version of Claude, then digested and verified by the authors. Though there are questions one can ask about attribution and incentives, this strikes me as a better approach than just putting undigested AI-generated content online.

Truly subquadratic time for 3SUM is a problem I have thought about on and off for many years. Now a breakthrough result has been announced by Josh Alman and Virginia Vassilevska Williams! arxiv.org/abs/2610.06783

The Gaussian mechanism is a key technique in differential privacy, used to make a bounded-sensitivity vector differentially privacy. Its analysis usually assumes the ability to perform computations with real numbers, so implementations must approximate the mechanism without breaking its guarantees.

4) Its coordinate-wise noise distribution is unbiased and has small total variation distance from Gaussian noise. Interestingly, the starting point for this work was only property 3), following up on the very nice work by Canonne, Su, and Vadhan in ITCS '25. The other properties were byproducts!

The Gaussian mechanism is a key technique in differential privacy, used to make a bounded-sensitivity vector differentially privacy. Its analysis usually assumes the ability to perform computations with real numbers, so implementations must approximate the mechanism without breaking its guarantees.

In a new fun collaboration with Nikita Kalinin from ISTA, we have described a new alternative, the Dithered Gaussian mechanism, which has a number of advantages: 1) It is a post processing of the Gaussian mechanism and therefore inherits its privacy guarantees and Gaussian based privacy accounting.

The Gaussian mechanism is a key technique in differential privacy, used to make a bounded-sensitivity vector differentially privacy. Its analysis usually assumes the ability to perform computations with real numbers, so implementations must approximate the mechanism without breaking its guarantees.

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).

Since a BLT is a sandwich, and our data structure is filled to the limit with contents, we found it suitable to name it the "Stuffed IBLT". It is always good to see such long-running projects come to a conclusion, and the (tasty?) paper is now out on arXiv: arxiv.org/abs/2609.17487

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).

Back in 2022, Stefan Walzer visited Copenhagen and we talked about getting "best of both worlds" results with near-optimal space efficiency and efficient operations. Our first thought was to combine the known techniques to a form of bucketed IBLTs. But it turns out there is a better way...

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).

IBLTs can be used for *set reconciliation*, where we must compute the symmetric difference A∆B of multisets A and B held by different servers. If A∆B is small enough, IBLT(A)-IBLT(B) can be used to recover its elements. Servers need only communicate the IBLTs, independent of the sizes of A and B.

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.

I have known about this result for about 3 years, but since Thomas and Jakob are working in industry it took some time to get the paper written. A nice contrast to the rush to publish that we see too often, and as a bonus the paper is (partly) Lean formalized. Congratulations on this achievement!

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.

A 1972 result by Rabin and Winograd showed that fewer multiplications suffice for large enough n. Specifically, n/2+O(log n) multiplications suffice for polynomials over the reals (as well as some other fields). But the O(log n) term makes the method impractical for low-degree polynomials.

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!

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.

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.

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 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.

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!

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.

The workshop is organized by @amartyasanyal.bsky.social, @claudiorlandi.bsky.social and myself. See the call for contributions as well as registration information on the workshop web page p1dpml.github.io/workshops/wo...