iiinova — where your digital self keeps evolving

Reposted by Thatchaphol Saranurak

Ryan O'Donnell @booleananalysis.bsky.social · 10/09/2026

Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos. We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.

youtube.com

Complexity Theory At Carnegie Mellon

05717

Reposted by Thatchaphol Saranurak

Clément Canonne @ccanonne.github.io · 01/08/2026

"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/

620351

Reposted by Thatchaphol Saranurak

Chris Peikert @chrispeikert.bsky.social · 02/08/2026

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

3407

Thatchaphol Saranurak @eigx.bsky.social · 23/07/2026

Wow, this is insightful. I also admire the way Sophie objectively self-criticizes her own work and her area.

0111

Thatchaphol Saranurak @eigx.bsky.social · 14/07/2026

breakthrough in binary search trees!

0133

Thatchaphol Saranurak @eigx.bsky.social · 12/07/2026

We show the first poly-time algorithm for *expander decomposition* that is optimal up to only a log^{o(1)}(n) factor. Known algorithms are worse than the optimal existential bound by at least a log^{0.5}n factor. Our approach is very different too. www.youtube.com/watch?v=70bL...

youtube.com

Expander Decomposition with Almost Optimal Overhead (short version)

YouTube video by Thatchaphol Saranurak

1161

Reposted by Thatchaphol Saranurak

School of Computer Science, University of Sydney @sydneycompsci.bsky.social · 01/07/2026

🚨📣 Clément Canonne and Sasha Rubin are organising a three-day event, "Sydney TCS Winter School 2026: Interactive Proofs and PCP Theorem" on July 22–24, 2026. Open to UG, Masters, and PhD students. Free attendance, but registration required! sites.google.com/view/sydney-...

sites.google.com

Sydney TCS Winter School 2026

📅 July 22—24, 2026 🌏 Sydney (Australia)

084

Reposted by Thatchaphol Saranurak

Joshua Grochow @joshuagrochow.bsky.social · 14/06/2026

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

1102

Reposted by Thatchaphol Saranurak

karthikcs.bsky.social @karthikcs.bsky.social · 14/06/2026

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

DIMACS :: List

073

Reposted by Thatchaphol Saranurak

Nutan Limaye @nutanlimaye.bsky.social · 02/06/2026

WACT 2026 in Copenhagen from Jun 2 to Jun 5 (started today!). Webpage: sites.google.com/view/wact202... YouTube channel: www.youtube.com/@WACT2026/pl...

1154

Thatchaphol Saranurak @eigx.bsky.social · 28/05/2026

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

kamathematics.wordpress.com

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…

0283

Reposted by Thatchaphol Saranurak

European Association for Theoretical Computer Science @eatcs.bsky.social · 27/04/2026

The 2026 Presburger Award for Young Scientists goes to Vincent Cohen-Addad and @gautamkamath.com 🥳🎉 You can read the laudatio here:

eatcs.org

Presburger Award 2026 – Laudatio

European Association for Theoretical Computer Science

1256

Reposted by Thatchaphol Saranurak

Huck Bennett @huckbennett.bsky.social · 19/04/2026

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

153

Thatchaphol Saranurak @eigx.bsky.social · 06/04/2026

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.

3578

Reposted by Thatchaphol Saranurak

karthikcs.bsky.social @karthikcs.bsky.social · 17/02/2026

1/3 Fine-Grained Complexity Fest at DIMACS this July! Three back-to-back workshops on Algebraic Techniques, String Algorithms, and Graph Algorithms in fine-grained complexity, with a terrific speaker lineup. Organized by @jalman.bsky.social , Elazar Goldenberg, and @eigx.bsky.social.

162

Reposted by Thatchaphol Saranurak

Clément Canonne @ccanonne.github.io · 06/02/2026

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

sigact.org

ACM SIGACT - Trevisan Award

12711

Thatchaphol Saranurak @eigx.bsky.social · 26/01/2026

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

youtube.com

Stanford AI Club: AI and the Future of Education

YouTube video by Stanford AI Club

050

Thatchaphol Saranurak @eigx.bsky.social · 16/12/2025

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

1110

Thatchaphol Saranurak @eigx.bsky.social · 09/12/2025

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

youtube.com

Frontiers of Graph Algorithms | Day 1 | 8th Dec 2025

YouTube video by CSAChannel IISc

0163

Reposted by Thatchaphol Saranurak

Jason Hartline @jasonhartline.bsky.social · 24/11/2025

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

theory.cs.northwestern.edu

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

042

Thatchaphol Saranurak @eigx.bsky.social · 21/11/2025

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

soda26.netlify.app

SODA/SOSA 2026 Schedule

043

Thatchaphol Saranurak @eigx.bsky.social · 09/11/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?...

youtu.be

What Is Understanding? – Geoffrey Hinton | IASEAI 2025

YouTube video by International Association for Safe & Ethical AI

040

Reposted by Thatchaphol Saranurak

let-all.com @let-all.com · 07/11/2025

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

11510

Reposted by Thatchaphol Saranurak

Clément Canonne @ccanonne.github.io · 30/10/2025

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

2373

Thatchaphol Saranurak @eigx.bsky.social · 23/10/2025

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

arxiv.org

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

1181

Reposted by Thatchaphol Saranurak

TCS+ @tcsplus.bsky.social · 17/10/2025

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

forms.gle

TCS+ RSVP: Ian Mertz (2025/22/08)

Title: A Random Walk Down Full Memory Lane

143

Reposted by Thatchaphol Saranurak

Steven Strogatz @stevenstrogatz.com · 22/08/2025

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

youtube.com

Interview with Steven Strogatz

YouTube video by Math-life balance

33412

Thatchaphol Saranurak @eigx.bsky.social · 18/07/2025

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

Lecture 4.1: Amortized Analysis: Bank account method, Binomial heaps, Hollow heaps

YouTube video by Thatchaphol Saranurak

152

Thatchaphol Saranurak @eigx.bsky.social · 18/07/2025

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.

youtube.com

Lecture 0: Introduction

YouTube video by Thatchaphol Saranurak

190

Reposted by Thatchaphol Saranurak

FOCS 2026 @focs2026.bsky.social · 13/07/2025

The list of accepted papers at #FOCS2025 is up! focs.computer.org/2025/accepte...

focs.computer.org

Accepted Papers – FOCS 2025

03615

Thatchaphol Saranurak @eigx.bsky.social · 06/07/2025

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 :)

youtube.com

LEADERSHIP LAB: The Craft of Writing Effectively

YouTube video by UChicago Social Sciences

1130

Reposted by Thatchaphol Saranurak

Waterloo's David R. Cheriton School of Computer Science @uwcheritoncs.bsky.social · 02/07/2025

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

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

0233

Reposted by Thatchaphol Saranurak

Barna Saha @barnacs.bsky.social · 18/06/2025

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

sigact.org

TCS for All

Theoretical Computer Science without Barriers

0187

Thatchaphol Saranurak @eigx.bsky.social · 07/06/2025

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

480

Reposted by Thatchaphol Saranurak

Clément Canonne @ccanonne.github.io · 03/06/2025

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

mpi-inf.mpg.de

Welcome - Max Planck Institute for Informatics

0154

Reposted by Thatchaphol Saranurak

Lance Fortnow @lance.fortnow.com · 31/05/2025

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

1144

Reposted by Thatchaphol Saranurak

Michael Dinitz @mdinitz.bsky.social · 31/05/2025

Incredibly well deserved!!

062

Reposted by Thatchaphol Saranurak

Ryan O'Donnell @booleananalysis.bsky.social · 17/05/2025

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

1324

Reposted by Thatchaphol Saranurak

Kasper Green Larsen @kasperglarsen.bsky.social · 30/04/2025

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

Accepted Papers

083

Reposted by Thatchaphol Saranurak

arxiv cs.DS @arxiv-cs-ds.bsky.social · 04/04/2025

Tuukka Korhonen Dynamic Treewidth in Logarithmic Time arxiv.org/abs/2504.02790

043

Reposted by Thatchaphol Saranurak

Samson Zhou @szhoucs.bsky.social · 04/04/2025

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)

waldo-workshop.github.io

Workshop on Algorithms for Large Data (Online) 2025

034