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?

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

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

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

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)

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

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, lots of interesting stuff! responsiblecomputing.org/forc-2025-ac...

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

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

Beautiful story in @quantamagazine.bsky.social on surprising space-efficient algorithms www.quantamagazine.org/catalytic-co...

Interesting policy for ACM CCS 2025: "Once the reviews have been sent to the authors the paper can not be withdrawn." I wonder why this policy was put in place, and what authors should do if they discover a fatal problem in their paper? www.sigsac.org/ccs/CCS2025/...

Interested in a career in theoretical computer science? Susanna de Rezende is hiring two PhD students and a postdoc for her group in Lund. Close proximity to the vibrant TCS community in Copenhagen. Apply March 16/31. derezende.github.io/openpositions/

This sounds very cool! The insight appears to be that if you can fool any computationally bounded adversaries, then you can fool any reasonable algo looking at the result of your computations. I.e., see the world as an "adversary", use cryptographic primitives to fool it. arxiv.org/abs/2502.130...

At STACS 2003 we published the first analysis of d-ary cuckoo hashing, but also described a less known open addressing technique called filter hashing which "can be used in combination with essentially any other hashing scheme to improve the space efficiency of the latter"

I had always thought that someone's age was the number of birthdays they had had. Then I learned that some countries count the day of birth as the first birthday. TIL another way used in some countries: Age is current year - birth year. So everyone born in the same year have the same age!

ChatGPT 4o's XeTaL abilities (going from a PDF to LaTeX source) are not perfect but pretty impressive and useful!

Contrary to popular belief it turns out that the street miniature artist AnonyMouse is NOT Elon Musk. sv.m.wikipedia.org/wiki/Anonymo...

Better late than never: Taking our 2nd year algorithms course into the multicore era!

Seen in Google Maps. I want this as a sign on my office door!

I wrote a ✨ new blog post ✨ about privacy in AI: five things that privacy experts know about AI, but that might not be so obvious outside our community 😶‍🌫️ Link here ️➡️ https://desfontain.es/blog/privacy-in-ai.html 🌈

And thanks to open source software, Casper Rysgaard has made a version with more details, such as author names. Enjoy! crowton.github.io/soda25program/