Super interesting thoughts and reflections on the recent breakthrough in fine-grained complexity!
I rarely post here these days but I wanted to share my reflections: people.csail.mit.edu/virgi/t…
Michael Dinitz retweeted
Come work with us @JHUCompSci! We're hiring tenure-track faculty in all areas, with a particular focus on
- AI systems
- AI safety and security
- AI reasoning and alignment
- AI ethics, policy, and governance
apply.interfolio.com/194231
(DMs are open if you have any questions)
Michael Dinitz retweeted
Before a bunch of arXiv papers point this out (which was a pretty well-known connection but not stated in the OpenAI paper):
The tight k-median approximation algorithm by OpenAI implies a tight and rather beautiful result for facility location, namely the optimal opening-cost vs. connection-cost tradeoff, everywhere on the curve (as illustrated here by AI).
🤖 Made with AI
Crazy TCS results: UGC, matrix multiplication, integer multiplication, k-median, …
OpenAI's Math post is up!
github.com/openai/math
Michael Dinitz retweeted
The what now?!
arxiv.org/abs/2610.06783v1
Michael Dinitz retweeted
Another very normal day, lol
APSP and 3SUM hypotheses are refuted: arxiv.org/abs/2610.06783v1
KLS conjecture is proved:
arxiv.org/abs/2610.01447v2
Wow!! Congrats @sahilsingla81 !!
An amazing result in online algorithms. I worked on this for over a decade and it is fantastic to see a solution that looks very clean! Also great to see an expert behind the wheels. Congratulations @sahilsingla81 arxiv.org/abs/2609.14555
Michael Dinitz retweeted
In “Ski Rental with Distributional Predictions of Unknown Quality,” Qiming Cui and @mdinitz revisit the central online problem of ski rental ⛷️ in the “algorithms with predictions” framework from the point of view of distributional predictions: arxiv.org/abs/2602.21104 (2/25)
Michael Dinitz retweeted
.@JHUBaseball in the house before their trip to the @NCAADIII College Baseball World Series! 🙌
Michael Dinitz retweeted
Very sad indeed. When I moved from Princeton to Columbia for grad school, I was *shocked* when I was told that I actually had to proctor my calc exams, and just not trust their "honor code".
At Princeton, the honor code genuinely meant something. In the first week of freshman year, we had to write an essay explaining in detail what the consequences of cheating were, why it didn't serve our long term interests, and how even if we weren't the ones cheating, if we knew that others were and didn't report it, we would be just as guilty. (I remember vividly, because my first attempt at such an essay was rejected as insufficiently detailed! I had to write a much longer version.) As a result, people really didn't cheat (as far as I knew; every year there was ~1 student kicked out of school for cheating).
It was something really special, it turned out; that's not how it works elsewhere. Sad to see further deterioration of the culture at Princeton.
Michael Dinitz retweeted
Probably lost at least a year of academic productivity to having kids and actually spending time with them. Only started going to academic events out of town after they turn 3. No regrets at all!
I talk to a lot of younger faculty who struggle balancing work and childcare, and sometimes pass on important professional opportunities as a result. When my first son was about to be born, I had a life-changing conversation with Peter Sarnak. I was living in NYC and teaching at Yale, commuting a few days a week.
Unprompted, he said:
“I’m going to give you some unsolicited advice. Take your entire salary and spend it on childcare. The cost of childcare won’t go up much, but if you prove good theorems, your salary will.”
I was a young assistant professor making ~$90K. My wife was finishing a postdoc and about to start a cardiology fellowship. It had never even occurred to me that we could afford a full-time nanny. But I knew better than to ignore Peter’s advice.
So we “splurged.” The nanny arrived at 8am. I handed her the baby and went to “work” (Starbucks), and worked as hard as I could until 6pm, when I went home to relieve her. It was a real cost at the time. But, as Peter predicted, it paid off.
Even though someone else cared for our son (eventually, sons) most of the day, we still had real evenings and weekends together — feeding, reading, bathing, playing. As the oldest is now getting ready for high school, I don’t feel like we missed out on any bonding in those early years.
And I indeed suffered many fewer professional losses than I would have otherwise. (That sabbatical in Paris will have to wait until they're in college...)
I’m not as good as Peter at forcing advice on people. So I’ll just leave this here, in case it helps someone else as much as it helped me.
Michael Dinitz retweeted
Happy Birthday, Hopkins!
Johns Hopkins turns 150 today. Here are just a few milestones that helped shape the university since 1876.
Explore more: 150.jhu.edu/
Michael Dinitz retweeted
As someone very closely involved with some of the history here (through my work with AIES and then FAccT conference from 2021-25), this all strikes me as precisely on point. Very much worth reading: transformernews.ai/p/the-lef…
A couple of months ago, @jachiam0 noted that "the left has completely abdicated their role in [the AI] discussion."
For @readtransformer today, the superb @kagankans diagnoses the full problem in depth — explaining exactly what people like Cory Doctorow, Emily Bender and Tyler Austin Harper get wrong — and why their sloppy thinking on this could lead to huge problems.
Michael Dinitz retweeted
Good read. Some part of the left are treating AI like some parts of the right treat climate change. They are just as wrong, but given AI's timescale, will be proven so much faster.
transformernews.ai/p/the-lef…
Postdoc positions available at the DSAI Institute @JohnsHopkins : ai.jhu.edu/careers/postdocto… . If you're interested in either differential privacy or algorithms with predictions, please get in touch!
Michael Dinitz retweeted
I just gave a tutorial on Design Templates for Dynamic Graph Algorithms at IISc in Bangalore.
The kindest words I received were "best tutorial I have listened to in the last 10 years." Hope it interests you.
Video: youtube.com/live/L8ev24gByZQ…
Slides: tinyurl.com/yetx3vxu
Michael Dinitz retweeted
Wonderful postmortem! Configuration change of a database you didn’t know about renders internet wide liveness failure.
1987: A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable
lamport.azurewebsites.net/pu…
We let the Internet down today. Here’s our technical post mortem on what happened. On behalf of the entire @Cloudflare team, I’m sorry. blog.cloudflare.com/18-novem…
































