Rasmus Pagh

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

SAT requires exhaustive search - Frontiers of Computer Science In this paper, we identify the distinction between non-brute-force computation and brute-force computation as the most fundamental problem in computer science. Subsequently, we prove, by the diagonali...

The ”Ethics declaration” is interesting and may shed some light on why the EiC was reluctant

link.springer.com/article/10.1...

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

First European Workshop on Differential Privacy September 17, 2026 At IST Austria

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!

Private Lossless Multiple Release Koufogiannis et al. (2016) showed a $\textit{gradual release}$ result for Laplace noise-based differentially private mechanisms: given an $\varepsilon$-DP release, a new release with privacy parameter...

In an upcoming #icml paper with @jdandersson.net, @lukasretschmeier.de, and Boel Nelson we extend this line of work to more general settings, e.g. allowing releases to be made adaptively in arbitrary order and supporting new noise distributions. The paper is now on arXiv: arxiv.org/abs/2505.22449

In 2015-2016 Koufogiannis, Han, and Pappas showed that multiple releases of Laplace and Gaussian mechanisms can be correlated such that having access to multiple releases exposes no more information than the least private release. In this sense we can create many releases with no loss in privacy!

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?

For Algorithms, a Little Memory Outweighs a Lot of Time | Quanta Magazine One computer scientist’s “stunning” proof is the first progress in 50 years on one of the most famous questions in computer science.

In case you didn't see it! www.quantamagazine.org/for-algorith...

PhD fellowship in Computer Science, PhD Project in Privacy and Cybersecurity PhD fellowship in Computer Science, PhD Project in Privacy and Cybersecurity Department of Computer Science, Faculty of SCIENCE, University of Copenhagen  

Are you an MSc student interested in privacy and security? Consider applying for this PhD position on metadata privacy with Boel Nelson
candidate.hr-manager.net/ApplicationI...

Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD Nikita P. Kalinin, Ryan McKenna, Jalaj Upadhyay, Christoph H. Lampert http://arxiv.org/abs/2505.12128 Matrix factorization mechanisms for differentially private training have emerged as a promising approach to improve model utility under privacy constraints. In practical settings, models are typically trained over multiple epochs, requiring matrix factorizations that account for repeated participation. Existing theoretical upper and lower bounds on multi-epoch factorization error leave a significant gap. In this work, we introduce a new explicit factorization method, Banded Inverse Square Root (BISR), which imposes a banded structure on the inverse correlation matrix. This factorization enables us to derive an explicit and tight characterization of the multi-epoch error. We further prove that BISR achieves asymptotically optimal error by matching the upper and lower bounds. Empirically, BISR performs on par with state-of-the-art factorization methods, while being simpler to implement, computationally efficient, and easier to analyze.

Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD

Nikita P. Kalinin, Ryan McKenna, Jalaj Upadhyay, Christoph H. Lampert

http://arxiv.org/abs/2505.12128

I heard the research submitted to #neurips is so hot they need about 2000 ACs to manage it

“Det är klart man är lite förvånad. Det kan man ju inte sticka under stol med, säger Axel Åhman i KAJ.” Som att bli förvånad över utfallet när man singlar slant…

It’s a stack of experiments, I guess, repeated many times until they finally reject the null hypothesis

not exactly rocket scientists | Far side comics, The far side, Far side cartoons This Pin was discovered by Jamie Bailey. Discover (and save!) your own Pins on Pinterest

Original: pin.it/4TIZhH1vi

Scientists standing in front of a bunch of p-values, most large but one smaller than 0.05. Caption: It's time we face reality, my friends... We're not exactly rugged scientists.

With apologies to Gary Larson

The Call for Papers (CfP) for #SODA26 is out: www.siam.org/conferences-...

The submission server is open: soda26.hotcrp.com

Deadline: ⏰ Monday, July 14, AoE (July 15, 11:59am UTC)

- Research is needed not just on core ML methods, but on AI in combination with cybersecurity, formal verification, human-computer interaction, and more.

The post explicitly does not address AI for military use that would "require a deeper analysis"

- AI has potential for harmful use but can also be used to defend against harm; ensuring a playing field giving defensive use an advantage is key
- Trying to limit the development of capability is likely to be counterproductive
- Regulation should address AI application, not capability

Post authors @randomwalker.bsky.social and @sayash.bsky.social do a great job at articulating the view. Some takeaways:
- Many societal issues associated with AI are not new, but have arisen in other contexts
- We can build on existing approaches to mitigating risk of harm through regulation

"AI as normal technology" captures a view that many of us hold but has not been very visible in the debates around AI. I used Substack's text-to-audio function for the first time to listen to www.aisnakeoil.com/p/ai-as-norm... (skipping the last 30 min. reading the reference list...)

Privacy Amplification by Subsampling Privacy Amplification by Subsampling is an important property of differential privacy. It is key to making many algorithms efficient – particularly in machine learning applications. Thus a lot of wor...

Insightful pair of blog posts by @stein.ke on #privacy amplification by subsampling: instead of running your privacy-preserving algo on the full dataset, run it on a random subset. Better!(?) Why, and what the limitations?

differentialprivacy.org/subsampling/
differentialprivacy.org/subsampling-...

European Sympsium on Algorithms 2025 will be held in Warsaw in September, as part of ALGO 2025. Do you have great work on design and analysis of algorithms? Submit it by April 23! algo-conference.org/2025/esa/

FORC 2025: Accepted Papers Hardness and Approximation Algorithms for Balanced Districting ProblemsPrathamesh Dharangutte, Jie Gao, Shang-En Huang and Fang-Yi Yu Privacy-Computation Trade-Offs in Private Repetition and Metase…

FORC 2025 accepted papers, lots of interesting stuff! responsiblecomputing.org/forc-2025-ac...

Ioana O. Bercea on X: "I’m recruiting! Please help spread the word! 2PhDs available at KTH Royal Institute of Technology, in the area of Theoretical Computer Science. Deadline is April 3rd, 2025. More details here: https://t.co/rbDT01n5XI" / X I’m recruiting! Please help spread the word! 2PhDs available at KTH Royal Institute of Technology, in the area of Theoretical Computer Science. Deadline is April 3rd, 2025. More details here: https://t.co/rbDT01n5XI

Opportunity to do a PhD in a wonderful city, at a great university, with a fantastic supervisor! x.com/ioanabercea/...

A glossary of differential privacy terms - Ted is writing things A list of short definitions of commonly used terms in differential privacy, with references for further reading.

I got annoyed couldn't find a good glossary of DP terms, so I wrote one: https://desfontain.es/blog/differential-privacy-glossary.html ✨

Simple definitions, links to further reading, and some mild snark about how bad we are at naming things sometimes 🙃

Trump’s Latest Weapon Against Critics: Destroying Their Lawyers When a president uses executive power to not just blacklist but effectively destroy a major law firm, solely for representing political opponents, it means he’s given up any pretense that he’s not …

There are a million horrible things happening all at once, but wanted to take a moment to focus on the exec order against Perkins Coie and how it's an attempt to make it difficult for anyone to use the legal process to challenge all this law breaking.

www.techdirt.com/2025/03/11/t...

🧵New paper on arXiv: Optimal Differentially Private Sampling of Unbounded Gaussians.

With @uwcheritoncs.bsky.social undergrad Valentio Iverson and PhD student Argyris Mouzakis (@argymouz.bsky.social).

The first O(d) algorithm for privately sampling arbitrary Gaussians! arxiv.org/abs/2503.01766 1/n