Thatchaphol Saranurak

New SIGACT award expository work, created in memory of Luca Trevisan: "intended to promote and recognize high-impact work expositing ideas and results from the Theory of Computation."

A wonderful initiative—consider nominating people!

⏰ Nomination deadline: April 10
sigact.org/prizes/trevi...

YouTube video by Stanford AI Club Stanford AI Club: AI and the Future of Education

Given AIs, I am still not sure how to teach algorithm classes today and in the future.

This discussion is quite nice, though.
www.youtube.com/watch?v=Vnz8...

It's first round interview season and the most useful thing I can recommend is to spend time on these: csfaculty.github.io

#FOCS2025
This is one of the best FOCS conferences I have attended.

Frontiers of Graph Algorithms | Day 1 | 8th Dec 2025 YouTube video by CSAChannel IISc

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: www.youtube.com/live/L8ev24g...
Slides: tinyurl.com/yetx3vxu

The 2025 Chicago Junior Theorists Workshop is December 8-9, hosted jointly by Northwestern and TTIC. Monday Dec 8 will be at TTIC and Tuesday Dec 9 will be at Northwestern (in the SkAI/NITMB in the Hancock tower in downtown Chicago). Register in advance.

theory.cs.northwestern.edu/2025/11/14/j...

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.

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

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

YouTube video by International Association for Safe & Ethical AI What Is Understanding? – Geoffrey Hinton | IASEAI 2025

This talk is really illuminating to me (especially around minute 7 to 11).

Clearly, I intuitively know what understanding is, but his explanation makes it much more explicit and makes sense.

youtu.be/6fvXWG9Auyg?...

Announcing the 7th Learning Theory Alliance mentoring workshop on November 20. Fully free & virtual!

Theme: Harnessing AI for Research, Learning, and Communicating

Ft @aaroth.bsky.social @andrejristeski.bsky.social @profericwong.bsky.social @ktalwar.bsky.social &more

Congratulations to Venkat Guruswami, new director of the Simons Institute for the Theory of Computing (@simonsinstitute.bsky.social)! And congrats to us, the Theoretical CS community, for having someone as good, dedicated, and wonderful as him at the helm of a place so important to us! #TCSSky

Nominate your final-year TCS PhD students or postdoc for the 2025 Chicago Junior Theorists Workshop (hosted by Northwestern and TTIC).

theory.cs.northwestern.edu/2025/10/30/2...

I hope this is a good step towards "clarity", an essential goal in science.

This is a joint work with the fantastic team: Aaron Bernstein, Joakim Blikstad, Jason Li, and Ta-Wei Tu.

Joakim and Ta-wei coded up the algorithm.
3/3

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs We give a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\{1,\dots,U\}$ in $\tilde{O}(n^{2}\log U)$ time, which is near-optima...

Both low-level implementation and analysis were previously very involved.

But our new paper simplifies both significantly.

Now
- Pretty readable for non-experts.
- Simple enough to code up fully in C++
- I am trying to teach it this semester arxiv.org/abs/2510.17182
2/3

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time We present a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\{1,\dots,U\}$ in $n^{2+o(1)}\log U$ time, which is almost optimal...

Can a max flow algorithm be both near-optimal and simple enough to teach?

Last year, we showed that the classical and intuitive augmenting-path approach can indeed be almost optimal for dense graphs.
arxiv.org/abs/2406.03648

But the result was not actually satisfying!
1/3

TCS+ RSVP: Ian Mertz (2025/22/08) Title: A Random Walk Down Full Memory Lane

📢 Our second TCS+ talk of the season will be Wednesday, Oct 22 (10amPT, 1pm ET, 19:00 CEST): Ian Mertz, from Charles University, will give guide us through "A Random Walk Down Full Memory Lane"!

RSVP to receive the link (available one day prior to the talk): forms.gle/495UjiLmQkkD...

YouTube video by Math-life balance Interview with Steven Strogatz

It was such a pleasure being a guest on "Math-Life Balance", a podcast devoted to interviews with mathematicians. Mura Yakerson is a fantastic interviewer! Check out our chat at www.youtube.com/watch?v=Gx8F... #mathsky

New Method Is the Fastest Way To Find the Best Routes | Quanta Magazine A canonical problem in computer science is to find the shortest route to every point in a network. A new approach beats the classic algorithm taught in textbooks.

This is very impressive. Breaking the sorting barrier for directed single source shortest paths
search.app/wnEUo

YouTube video by Thatchaphol Saranurak Lecture 4.1: Amortized Analysis: Bank account method, Binomial heaps, Hollow heaps

This lecture provides a gentle introduction to amortized analysis.

For experts: At the end, I explained Hollow Heaps, an optimal heap like Fibonacci heaps, but simpler! Surprisingly, I have not seen video lectures on this before.

www.youtube.com/watch?v=8mHa...

YouTube video by Thatchaphol Saranurak Lecture 0: Introduction

Math vs. Cooking:
What does it mean to do math/theory?

Here, I presented an analogy to cooking.
The goal was to help students understand how to effectively learn in theory classes.

www.youtube.com/watch?v=8Fz2...
(The discussion at 59:38)

I am curious to know if you think this makes sense.

The list of accepted papers at #FOCS2025 is up!

focs.computer.org/2025/accepte...

YouTube video by UChicago Social Sciences LEADERSHIP LAB: The Craft of Writing Effectively

Wow, this might be the best lecture on academic writing I've ever watched!
www.youtube.com/watch?v=vtIz...

If any of you have suggestions for good materials related to grant writing and/or mathematical writing, I would be interested :)

Professor Sepehr Assadi stands by a bench in Waterloo's Peter Russell Rock Garden.

Professor Sepehr Assadi has won the 2025 Presburger Award, a prestigious honour recognizing his exceptional contributions to theoretical computer science, in particular his pioneering work on establishing lower bounds for multi-pass streaming algorithms.

cs.uwaterloo.ca/news/sepehr-...

Omg

TCS for All Theoretical Computer Science without Barriers

This year TCS for All Inspiration talk will be given by Sofya Raskhodnikova, Boston University on June 27th at our STOC 2025 TCS for All Meeting. Join us. We are relocating the TCS for All Rising Star Workshop to FOCS 2025 this year. Stay tuned. SIGACT.org/tcsforall/
#stoc2025 @ccanonne.github.io

I also enjoy expositions (like some nice papers, surveys, and short textbooks).

But in my case, I put Schrijver's and Frank's combinatorial optimization books into NotebookLM. Honestly, I have only used them by looking up and never tried to read them for fun. Now, I can interact more with them.

3. editgpt.app has an excellent interface for polishing papers.

4. I failed to use AIs to help me solve any open problems (and even got tricked by their answers once). Have you succeeded? I am interested to hear.

3/3

1. For the literature search, I enjoy using the Deep Research of both ChatGPT and Gemini. (I still often go through the rabbit hole in Google Scholar.)

2. I upload many textbooks on the same topic to NotebookLM and ask questions. It is a fun way to learn and look up.

2/3

How do you use AI to help you do research?
I'd love to learn!

I'll share how to use them below.

1/3

This is amazing!