Tessera
Folgen

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/

49 Posts674 Follower110 Folgt
Clément Canonne@ccanonne.github.io · 4d ago

"We're all worried," as what it means to do research (in my field, Theoretical CS) seems to be shifting, and shifting fast. What to do? Senior researchers must lead by example, knowing that not everything will pan out. What I'm suggesting below may not work everywhere, but here's my own advice: 1/

Chris Peikert@chrispeikert.bsky.social · 3d ago

7/ Bottom line: If I were reviewing this for a top theory-of-CS conference, and the results bear out (as I expect them to), I would champion this for a Best Paper Award. (But I would also request a much more explanatory overview of the novel techniques in the intro...)

Joshua Grochow@joshuagrochow.bsky.social · 2mo ago

Good question! Let me try to explain; a short 🧵. Bipartite matching is one of the earliest nontrivial* problems with a poly-time algorithm. But that algorithm - augmenting paths - feels very sequential, hard to parallelize. * I mean something like: not obviously solved by O(1) nested loops 1/8

@karthikcs.bsky.social · 2mo ago

DIMACS is hosting not one, not two, but three workshops on fine-grained complexity next month, from July 20–31! Registration is free but required. To register, click each relevant workshop page on the DIMACS events page: dimacs.rutgers.edu/events/list Hope to see many of you there!

DIMACS :: List

dimacs.rutgers.edu

@karthikcs.bsky.social · 6mo ago

2/3 Workshops (dates + links): • Algebraic Techniques in FGC (July 20–22): dimacs.rutgers.edu/events/detai... • FGC of String Problems (July 23–25): dimacs.rutgers.edu/events/detai... • FGC of Graph Problems (July 27–31): dimacs.rutgers.edu/events/detai...

Thatchaphol Saranurak@eigx.bsky.social · 2mo ago

I fully agree with this post by @gautamkamath.com on how preparing talks is one of the best ways to upgrade my own thinking. So, I certainly do not want to waste that opportunity by delegating it to AI. kamathematics.wordpress.com/2026/05/27/m...

Making a talk, without and with AI

Some of the discussion online has been about how not to use AI in making academic talks (see, e.g., this post by Jessica Hullman). A junior researcher asked my opinion on using AI to help make slid…

kamathematics.wordpress.com

Huck Bennett@huckbennett.bsky.social · 4mo ago

This is very nice recognition of Hal Gabow! Hal spent his whole career as faculty at CU Boulder, and his legacy looms large for us. (Hal retired in 2008, and I unfortunately have never gotten a chance to meet him.)

Anupam Gupta@anupamg.bsky.social · 4mo ago

The ACM Transactions on Algos now has the Harold N. Gabow Annual Best Paper Award, for research contributions with lasting significance in algos. Hal Gabow, an amazing algos researcher, was founding editor of TALG, and helped establish this award. Thanks Hal! (Submit yr best papers to TALG!) 1/n

Thatchaphol Saranurak@eigx.bsky.social · 4mo ago

I poured my soul into building this course last fall: 📚 Graph Algorithms via Graph Decomposition 📚 Graph decomposition has been a powerful framework in graph algorithms for over 20 years, but the literature is scattered and technical. Thus, I tried to organize part of it into one coherent story.

Jason Hartline@jasonhartline.bsky.social · 8mo ago

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

Junior Theorists Workshop 2025 | Northwestern CS Theory Group

Synopsis: The Chicago Junior Theorists Workshop 2025 is being held jointly by Northwestern University and Toyota Technological Institute at Chicago on ...

theory.cs.northwestern.edu

Jason Hartline@jasonhartline.bsky.social · 9mo ago

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

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

Thatchaphol Saranurak@eigx.bsky.social · 10mo ago

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

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