Thatchaphol Saranurak
@eigx.bsky.social
Assistant Professor at the University of Michigan.
I design fast graph algorithms in dynamic/distributed/local settings.
https://sites.google.com/site/thsaranurak/
I design fast graph algorithms in dynamic/distributed/local settings.
https://sites.google.com/site/thsaranurak/
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?...
Clearly, I intuitively know what understanding is, but his explanation makes it much more explicit and makes sense.
youtu.be/6fvXWG9Auyg?...
What Is Understanding? – Geoffrey Hinton | IASEAI 2025
YouTube video by International Association for Safe & Ethical AI
youtu.be
November 9, 2025 at 2:43 AM
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?...
Clearly, I intuitively know what understanding is, but his explanation makes it much more explicit and makes sense.
youtu.be/6fvXWG9Auyg?...
Reposted by Thatchaphol Saranurak
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
Theme: Harnessing AI for Research, Learning, and Communicating
Ft @aaroth.bsky.social @andrejristeski.bsky.social @profericwong.bsky.social @ktalwar.bsky.social &more
November 7, 2025 at 4:34 PM
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
Theme: Harnessing AI for Research, Learning, and Communicating
Ft @aaroth.bsky.social @andrejristeski.bsky.social @profericwong.bsky.social @ktalwar.bsky.social &more
Reposted by Thatchaphol Saranurak
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
October 30, 2025 at 8:18 PM
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
Reposted by Thatchaphol Saranurak
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...
theory.cs.northwestern.edu/2025/10/30/2...
2025 Chicago Junior Theorists Workshop (Call for Nominations) | Northwestern CS Theory Group
We seek nominations of outstanding final-year Ph.D. students and postdocs to attend and present their recent research at the 2025 Chicago Junior Theoris...
theory.cs.northwestern.edu
October 30, 2025 at 8:24 PM
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...
theory.cs.northwestern.edu/2025/10/30/2...
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
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
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...
arxiv.org
October 23, 2025 at 4:47 AM
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
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
Reposted by Thatchaphol Saranurak
📢 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...
RSVP to receive the link (available one day prior to the talk): forms.gle/495UjiLmQkkD...
TCS+ RSVP: Ian Mertz (2025/22/08)
Title: A Random Walk Down Full Memory Lane
forms.gle
October 17, 2025 at 7:47 PM
📢 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...
RSVP to receive the link (available one day prior to the talk): forms.gle/495UjiLmQkkD...
Reposted by Thatchaphol Saranurak
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
Interview with Steven Strogatz
YouTube video by Math-life balance
www.youtube.com
August 22, 2025 at 8:33 PM
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
Reposted by Thatchaphol Saranurak
This is very impressive. Breaking the sorting barrier for directed single source shortest paths
search.app/wnEUo
search.app/wnEUo
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.
search.app
August 6, 2025 at 5:33 PM
This is very impressive. Breaking the sorting barrier for directed single source shortest paths
search.app/wnEUo
search.app/wnEUo
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...
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...
Lecture 4.1: Amortized Analysis: Bank account method, Binomial heaps, Hollow heaps
YouTube video by Thatchaphol Saranurak
www.youtube.com
July 18, 2025 at 4:32 PM
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...
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...
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.
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.
Lecture 0: Introduction
YouTube video by Thatchaphol Saranurak
www.youtube.com
July 18, 2025 at 2:26 PM
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.
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.
Reposted by Thatchaphol Saranurak
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 :)
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 :)
LEADERSHIP LAB: The Craft of Writing Effectively
YouTube video by UChicago Social Sciences
www.youtube.com
July 6, 2025 at 9:22 PM
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 :)
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 :)
Reposted by Thatchaphol Saranurak
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-...
cs.uwaterloo.ca/news/sepehr-...
July 2, 2025 at 2:28 PM
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-...
cs.uwaterloo.ca/news/sepehr-...
Omg
NEW: NSF will be kicked out of their building. Announcement will be made tomorrow by HUD Sec. and Governor of VA. HUD will take over the NSF building over the next two years.
NSF staffer: "There is no planning for NSF, no identified future location, appropriation for a new building or a move."
NSF staffer: "There is no planning for NSF, no identified future location, appropriation for a new building or a move."
June 24, 2025 at 11:31 PM
Omg
Reposted by Thatchaphol Saranurak
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
#stoc2025 @ccanonne.github.io
TCS for All
Theoretical Computer Science without Barriers
SIGACT.org
June 18, 2025 at 2:33 AM
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
#stoc2025 @ccanonne.github.io
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
I'd love to learn!
I'll share how to use them below.
1/3
June 7, 2025 at 2:48 AM
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
I'd love to learn!
I'll share how to use them below.
1/3
Reposted by Thatchaphol Saranurak
This graduate-level summer school at the Max Planck Institute (Aug 18–22) on "Graph Decompositions and Efficient Algorithms" looks pretty good! Ft. Maria Chudnovsky, Michał Pilipczuk, and Thatchaphol Saranurak (@eigx.bsky.social)
Travel grant applications: June 30
www.mpi-inf.mpg.de/departments/...
Travel grant applications: June 30
www.mpi-inf.mpg.de/departments/...
Welcome - Max Planck Institute for Informatics
www.mpi-inf.mpg.de
June 3, 2025 at 9:28 AM
This graduate-level summer school at the Max Planck Institute (Aug 18–22) on "Graph Decompositions and Efficient Algorithms" looks pretty good! Ft. Maria Chudnovsky, Michał Pilipczuk, and Thatchaphol Saranurak (@eigx.bsky.social)
Travel grant applications: June 30
www.mpi-inf.mpg.de/departments/...
Travel grant applications: June 30
www.mpi-inf.mpg.de/departments/...
Reposted by Thatchaphol Saranurak
Tracy Kimbrel, former National Science Foundation program director extraordinaire, will receive the 2025 ACM SIGACT Distinguished Service Award. He spearheaded programs such as TRIPODS (foundations of data science) and AitF (Algorithms in the Field).
1/2
1/2
May 31, 2025 at 4:16 PM
Tracy Kimbrel, former National Science Foundation program director extraordinaire, will receive the 2025 ACM SIGACT Distinguished Service Award. He spearheaded programs such as TRIPODS (foundations of data science) and AitF (Algorithms in the Field).
1/2
1/2
Reposted by Thatchaphol Saranurak
Incredibly well deserved!!
Huge congratulations to Tracy Kimbrel, who received the 2025 ACM SIGACT Service Award 🏆 for his time, dedication, and advocacy as Program Director for the Algorithmic Foundations (AF) program at the NSF!
sigact.org/prizes/servi... #TCSSky
sigact.org/prizes/servi... #TCSSky
2025 ACM-SIGACT Distinguished Service Award
sigact.org
May 31, 2025 at 8:53 AM
Incredibly well deserved!!
Reposted by Thatchaphol Saranurak
This!
I like to say,
"Let p|A denote distribution p conditioned on event A.
Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A.
Except you don't have to imagine, because it's literally our world!
Now explore probabilistic algorithms in this world."
I like to say,
"Let p|A denote distribution p conditioned on event A.
Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A.
Except you don't have to imagine, because it's literally our world!
Now explore probabilistic algorithms in this world."
May 17, 2025 at 11:38 AM
This!
I like to say,
"Let p|A denote distribution p conditioned on event A.
Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A.
Except you don't have to imagine, because it's literally our world!
Now explore probabilistic algorithms in this world."
I like to say,
"Let p|A denote distribution p conditioned on event A.
Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A.
Except you don't have to imagine, because it's literally our world!
Now explore probabilistic algorithms in this world."
Reposted by Thatchaphol Saranurak
Accepted papers for ICALP'25 is now online! Please register for amazing program and come visit us here in Aarhus!
conferences.au.dk/icalp2025/ac...
conferences.au.dk/icalp2025/ac...
Accepted Papers
conferences.au.dk
April 30, 2025 at 9:26 AM
Accepted papers for ICALP'25 is now online! Please register for amazing program and come visit us here in Aarhus!
conferences.au.dk/icalp2025/ac...
conferences.au.dk/icalp2025/ac...
Reposted by Thatchaphol Saranurak
April 4, 2025 at 5:04 AM
Reposted by Thatchaphol Saranurak
Taking a break from the submission season? Swing by the Workshop on Algorithms for Large Data (Online), WALDO 2025 🗓️ April 14—16: waldo-workshop.github.io/2025.html
Registration is free! (but necessary by April 7)
Registration is free! (but necessary by April 7)
Workshop on Algorithms for Large Data (Online) 2025
waldo-workshop.github.io
April 4, 2025 at 6:44 AM
Taking a break from the submission season? Swing by the Workshop on Algorithms for Large Data (Online), WALDO 2025 🗓️ April 14—16: waldo-workshop.github.io/2025.html
Registration is free! (but necessary by April 7)
Registration is free! (but necessary by April 7)
An alternative name for log* that I quite like
Logging depth?
April 3, 2025 at 12:42 PM
An alternative name for log* that I quite like
Reposted by Thatchaphol Saranurak
I am very much looking forward to giving this talk at TCS+, which is one of my favourite seminars. Thanks for inviting me!
I am very excited about this talk: First, Zero-Knowledge proofs are basically magic. Second, PCPs are nothing short of sorcery. Third, Tom is too good at everything not to secretly be a wizard.
It's going to be awesome!
forms.gle/Zwyn13NkKNSr...
It's going to be awesome!
forms.gle/Zwyn13NkKNSr...
March 17, 2025 at 10:38 AM
I am very much looking forward to giving this talk at TCS+, which is one of my favourite seminars. Thanks for inviting me!