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!

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.

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

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

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.

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

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

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!

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

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

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!

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

The deadline for BARC's annual call for PhD positions is soon (January 10)!

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

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

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

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:

Announcing (w @adamsmith.xyz @thejonullman.bsky.social) the 2025 edition of the Foundations of Responsible Computing Job Market Profiles! Check out 40 job market candidates in mathematical research in computation and society writ large! Link: drive.google.com/file/d/1zvsr...

Getting ready to celebrate 150 years of women at @ucph.bsky.social with the Wave workshop, focusing on algorithmic research barc.ku.dk/wave-confere...

In anticipation of this week’s Nobel prizes? Sign next to UCPH Nobel prize reserved parking says ”Beware of crossing traffic”

My run yesterday passed by Malmö Stadium, where West Germany defeated Argentina 3-1 in the 1958 soccer World Cup, after an early Argentinian goal. Sadly the stadium will soon be demolished to make room for new sports facilities.

We are alarmed by reports that Germany is on the verge of a catastrophic about-face, reversing its longstanding and principled opposition to the EU’s Chat Control proposal which, if passed, could spell the end of the right to privacy in Europe. signal.org/blog/pdfs/ge...

Proud to learn that BARC alumnus Jakub Tětek was chosen as one of 4 winners (out of 260 PhD theses) of the @ucph.bsky.social SCIENCE PhD award. Congratulations to Jakub and the other winners! kunet.ku.dk/newsroom/new...

150 years ago the first women were enrolled at University of Copenhagen. To celebrate, four of my awesome BARC colleagues are arranging the WAVE workshop on October 10th. Amazing speakers and panelists, full-day catering, and Copenhagen culture night in the evening! Join us! t.co/zIeUnYVXMC

Happy to learn that work on dynamic range filters by my frequent collaborators Navid Eslani, Ioana Bercea, & Niv Dayan has been recognized with a best paper award at VLDB! The paper is a great example of theoretical understanding informing practical engineering of data structures. Congratulations!

An 8% funding rate is... tough

Only discovered today that AirCloak, the company behind the Diffix system for differential privacy-inspired query answering, is no longer operating. An open source project focusing on synthetic data, made in collaboration with MPI-SWS, has inherited the Diffix name.

A thought experiment: What if every sufficiently expensive machine learning model was required to immediately be open-sourced? I explore this in a new blog post: togelius.blogspot.com/2025/08/mand...

Space flight as a normal technology

Over the last few months we have begun to see glimpses of how our new ladders can be used to build even longer ladders. The improvement is slow for now, but undeniable. Developing a ladder to the stars is now in sight. (Paraphrasing www.meta.com/superintelli...)

While Helen Toner is more sympathetic to the grandiose possibilities of AI than I am, her talk here is a terrific and highly accessible overview of the core debates happening in the AI research community. Worth your time. open.substack.com/pub/helenton...

Another great piece in @quantamagazine.bsky.social, this time on new surprising algorithms for shortest paths. With quotes from BARC head and shortest path grand-old-man Mikkel Thorup

The Call for Workshops for #FOCS2025 is up! Submit a proposal by September 5! 📋 focs.computer.org/2025/call-fo... Workshop chairs: Mohsen Ghaffari and Dakshita Khurana

DARA (Danish Advanced Research Academy) is a new initiative in which exceptional STEM candidates can get fully funded PhD scholarships at Danish universities. Those who are interested in applying should reach out to potential supervisors as soon as possible. daracademy.dk/fellowship/f...

Finally a workshop on Differential Privacy in Europe! Organized by Monika Henzinger at IST Austria next year in September, so reserve the date! Monika’s STOC keynote, where the workshop was announced, was about the intersection of privacy and dynamic algorithms. Lots of questions in this space!

Jonas Klausen hashing out the details at his PhD defense at BARC yesterday. Congratulations to Jonas for a successful defense!

Comprehensive survey of correlated noise mechanisms and their application in private machine learning!

Differential privacy usually deals with releasing information about a dataset at a fixed privacy level with as high utility as possible. In some settings there is a need to have *multiple* releases at different levels of privacy/trust, but how can this be done without degrading privacy?