Can we flip the script so that AI creates interesting open math problems for humans to work on?

Very proud of my awesome student Nikhil Shagrithaya @nikhilshagri.bsky.social for successfully defending his Ph.D. thesis! This is a culmination of great work on challenging core questions in coding theory. Nikhil's research has been published in top CS venues, including FOCS and STOC conferences.

I got a whimsical suggested reply from my phone today

Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, Da Wei Zheng: DAG Covers: The Steiner Point Effect https://arxiv.org/abs/2604.04186 https://arxiv.org/pdf/2604.04186 https://arxiv.org/html/2604.04186

Greg Bodwin, Luba Samborska: Improved Upper Bounds for the Directed Flow-Cut Gap https://arxiv.org/abs/2604.03412 https://arxiv.org/pdf/2604.03412 https://arxiv.org/html/2604.03412

Nikhil Bansal, Milind Prabhu, Sahil Singla, Siddharth M. Sundaram: Online Graph Balancing and the Power of Two Choices https://arxiv.org/abs/2604.04159 https://arxiv.org/pdf/2604.04159 https://arxiv.org/html/2604.04159

Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak: DAG Projections: Reducing Distance and Flow Problems to DAGs https://arxiv.org/abs/2604.04752 https://arxiv.org/pdf/2604.04752 https://arxiv.org/html/2604.04752

Our snow soufflé has risen.

Lenore Blum@lenoreblum.bsky.social · 6mo ago

This is a photo of our backyard in Pittsburgh just now. We were supposed to fly to California today. Snow can be beautiful and calming.

I tried to access epubs.siam.org from the SODA hotel WiFi and it seems like we have all been blocked haha #soda26

The info and slides of the 18 🎓 "Graduating Bits" participants are now available on the website! Look at them, hire them! focs.computer.org/2025/graduat...

Stoked about the new work with Édouard Bonnet, Tuukka Korhonen, Jason Li, and Tomáš Masařík: a simple linear time algorithm to find a balanced separator in minor-free graphs. A more detailed blog post, giving a complete pseudocode: minorfree.github.io/SepLinear/ Paper: arxiv.org/abs/2512.01587

The directed next-to-shortest path problem was solved by 2 undergrads! arxiv.org/abs/2511.04345 Look out for Kuowen Chen and Yiran Zhang this PhD application cycle.

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs

Given a graph and a pair of terminals $s$, $t$, the next-to-shortest path problem asks for an $s\!\to \!t$ (simple) path that is shortest among all not shortest $s\!\to \!t$ paths (if one exists). Thi...

arxiv.org

\'Edouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, Tom\'a\v{s} Masa\v{r}\'ik: Separator Theorem for Minor-Free Graphs in Linear Time https://arxiv.org/abs/2512.01587 https://arxiv.org/pdf/2512.01587 https://arxiv.org/html/2512.01587

I hate conference deadlines, but somehow, deadlines make magic happen. A week ago, we had a jumble of texts, but now we have what looks like a nice paper.

The connection between distributed algorithms and descriptive set theory featured in Quanta: www.quantamagazine.org/a-new-bridge...

A New Bridge Links the Strange Math of Infinity to Computer Science | Quanta Magazine

Descriptive set theorists study the niche mathematics of infinity. Now, they’ve shown that their problems can be rewritten in the concrete language of algorithms.

quantamagazine.org

I used AI to create an easier-to-navigate schedule for SODA and SOSA 26 here: soda26.netlify.app The original one is hard to see the overview. meetings.siam.org/program.cfm?...

Kuowen Chen, Nicole Wein, Yiran Zhang: A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs https://arxiv.org/abs/2511.04345 https://arxiv.org/pdf/2511.04345 https://arxiv.org/html/2511.04345

📢 Our first TCS+ talk of the season will be Wednesday, Oct 8 (10amPT, 1pm ET, 19:00 CEST): Janani Sundaresan, from U Waterloo, will tell us how "Distributed Triangle Detection is Hard in Few Rounds"! RSVP to receive the link (available one day prior to the talk): forms.gle/sHdV8uoKYVpq... #TCSSky

TCS+ RSVP: Janani Sundaresan (2025/10/08)

Title: Distributed Triangle Detection is Hard in Few Rounds

forms.gle

Some questions on spanners in my talk at the Simons Institute. Since the talk, progress has been made on a few questions, but most are open. minorfree.github.io/SpannerQues/