Thatchaphol Saranurak

Assistant Professor at @UMichCSE.
I design fast graph algorithms in dynamic/distributed/local settings.

[Yuval Filmus @YFilmus]

OpenAI recently proved that 𝜔≤2.25. Their proof is outlandish, using Strassen's theory of asymptotic spectra. Sergey Gusev recently gave a constructive proof of the same bound, which obviates the use of asymptotic spectra. However, their work is also quite opaque.

[Anupam Gupta @anupamg]

Thanks to the team for the amazing work! From my side, the special shout-out goes to Henry Fleischman, whose visit to @NYU_Courant last summer led first to a faster optimal FPT algorithm, and eventually resulted in this result.

[Thatchaphol Saranurak @eig]

TCS values and goals: "what do we stand for, what do we do, and why?" asked by Clément Canonne https://t.co/Az7Jb9xDEQ

[Thatchaphol Saranurak @eig]

Details about the STOC'27 video submission are now posted:
https://t.co/qS6zqtKKEI

Our community needs experiments, and this is the one I have been advocating for. We, as a community, will see how it goes and will adapt.

[Jelani Nelson @minilek]

Mike was my colleague at Berkeley, and he's been fairly skeptical of deep learning's trajectory for years. Most scientists are skeptics, and it can take a big shock to get someone to consider a possibility that goes against the anchoring effect coded in our DNA.

I too was somewhat of a skeptic until ~6 months ago, and people ask me all the time why I joined Anthropic.

It started in April, when a friend I've known for 20 yrs messaged me saying he'd be in the Bay Area in a week, and he suggested we meet up. I invited him to my house for dinner, and he told me he had just joined Anthropic. He said the models were becoming increasingly more capable, and he believed both that they'd soon be smarter than him and also that all intellectual work would be highly devalued in the near future, and lastly that society was not at all ready for what's coming.

I'd of course heard claims similar to this before, but not from a friend I'd known for this long, and who I trusted, at my dining room table. It was the initial shock needed to destabilize my own anchoring. Also, I've been fortunate to work with and/or mentor many smart people in my life (e.g. Fields medalists, a 4x Putnam Fellow, IOI first place winners, etc.), so I feel pretty calibrated in recognizing very smart people, and this was someone who is definitely very smart and with impressive such credentials. So, it was hard to ignore this friend saying the models would be smarter than even him in particular.

After that dinner, I decided to do an informal survey, calling and meeting up with a lot of my friends who now work on improving model capabilities at these frontier labs. They all agreed with that first friend. These were all people I'd known 10, 15, 20 years, who mentored me, or I mentored them, or we met professionally in academia. These are people I trust, and their beliefs on this topic were consistent.

I then spent a whole lot of time understanding the missions of different companies, and talking to current and former employees and people in leadership. I read Dario's (long) essays and watched videos on YouTube of company leaders being interviewed. Anthropic's stated mission "to ensure that the world safely makes the transition through transformative AI" felt like exactly the right guiding principle to handle such a society-disrupting technology, and everyone I spoke to at the company was very aligned with this mission. It's easily the most mission-focused place I've ever been at, and everyone takes the work extremely seriously and with a profound sense of responsibility.

And now here I am. And being on the inside, the pace of progress has surprised me more than I first imagined. The moment that pure mathematicians are in, to me, is just a microcosm of what I predict a much larger of society will be grappling with in the not too distant future, and I really hope our leaders and the general public internalize sooner than later just how significant a moment we're in.

[Andrej Karpathy @karpathy]

Dusting off this tweet from April because this gap in shared understanding of LLM capability is *widening*. It's now less "two groups of people speaking past each other" and more a sharp funnel.

- Napkin math somewhere around 6B people (~75% of the population) have barely come in contact with LLMs at all.
- Around 1-2B (~20%) are casual and infrequent users of free-tier ChatGPT-like products. This group sees derpy chatbots and treats them a bit like a better Google search, a writing aid, or etc. Maybe an agent tries to book you a flight. I have non-tech friends who (reasonably, imo) say they have not much use for it at all. Even many professionals outside of math&code are in this tier. For example, execs and many other functions spend a lot of their time talking to other people, so while they understand what is happening intellectually, it is still second-hand and a bit abstract.
- Now we get to professional use of frontier-grade LLMs in math&code. Somewhere around 20M people (0.2%) see first-hand that large, complex projects that used to take them weeks/months can now be completed by agents with a prompt. Building apps, copying apps, translating apps, decompiling apps from binaries... This has all happened very quickly and recently - less than 1 year ago, I was writing code manually by hand, typing memorized computer code commands into a code editor character by character, occasionally pressing Tab to autocomplete a little chunk of code.
- And finally we get to the ~5,000 people (~0.00006%) with access to frontier-grade systems internally. The external world has seen the preview. It looks like swarms of thousands of agents collaborating over weeks on software mega projects: minting zero days, running cyber attacks and defenses at machine speeds, discovering new science, advancing the frontier of mathematics. Things that would have taken top professionals in the industry years of work. Meanwhile, human review and comprehension are starting to fall behind. For example, people are still involved in the "archeology" of the OpenAI-HF incident from many months ago. Mathematicians may be poring over the 722 manuscripts on frontier mathematics for a while.

The funnel is driven by a combination of factors:
1. The impact scales with ambition, problem size, and horizon. A question with a paragraph answer barely stresses the system. You need a reservoir of big, difficult problems that you really care about. This aspect drives the consumer / professional dimension of the funnel.
2. The jaggedness of the system (which I have written about a lot separately). Capability peaks in domains that are digital, verifiable and economically valuable. This is because LLM capability emerges from reinforcement learning on verifiable rewards on a curated environment mixture driven by revenue potential. This aspect primarily drives the area (e.g. math&code) dimension of the funnel.
3. Access. Free-tier, paid-tier, internal.

So this is the weirdness of the moment. The general public has mostly not interacted with these systems. When they have, it looks like a derpy chatbot. The majority of professionals still see only a modest uplift. And a small sliver of professionals are experiencing the vertigo of the curve going vertical. And it is all happening at the same time.

[Thatchaphol Saranurak @eig]

@gautamcgoel @BooleanAnalysis @AcerFur This is so that we can store a location of a memory in one word and perform a random access.

[Jared Duker Lichtman @jdlichtman]

To spell it out explicitly:

In May: 1 proof
https://t.co/QCWddvw6AV
In August: 10 proofs
https://t.co/Fc7u0HZ6LU
Now in October: 100's of proofs
https://t.co/xscCxxFbFS

Next up in a few months: 1000's of proofs!

[Ryan Williams @rrwilliams.bsky.social @rrwilliams]

For what it's worth, OpenAI's one-tape TM simulation (assuming correct) immediately implies RAM time t is in SPACE[t^{4/5}]
https://t.co/ralQgCkNG4
Not sure why they didn't mention this corollary! That was the whole point of my question.

[Thatchaphol Saranurak @eig]

Another very normal day, lol

APSP and 3SUM hypotheses are refuted: https://t.co/dJKSLOxDtb
KLS conjecture is proved:
https://t.co/I6qa5MLSjt

[Andrew Curran @AndrewCurran_]

Scott Aaronson is now teaching Alignment Theory.

[Thatchaphol Saranurak @eig]

Among many recent essays on the future of math, I agree with this one a lot.

[Christian Szegedy @ChrSzegedy]

Reading all those recent beautiful essays by Terry Tao, Kevin Buzzard and @wtgowers, I could not resist, but write up my deeply personal perspective on how I perceive and see things:

https://t.co/fvWb4b7jGU

[David Savitt @dsavitt]

Hello, world! There is a new repository for works in math and TCS: https://t.co/Br3fKoLgn6, now in public beta. Please try it out and submit something! We welcome your feedback while we build and improve it.

[Alex Kontorovich @AlexKontorovich]

Sept 4 (Friday of Labor Day weekend): FLT formalization announced by Anthropic

Sept 7/8: Tristan+Levent -> OpenAI announce Navier-Stokes

But somehow amidst all the commotion, we all seemed to have missed the following (!!!).

Sept 6: Lech Mazur claims an AI-generated proof that a positive proportion of numbers go back to 1 under Collatz!! And it's Lean-formalized. I went through the Lean (or rather, had my AI do it) and I think it's right. Now I'm trying to make sense of the math (doesn't look like anything is too hard, just a lot of arguments, building on top of Terry's earlier work).

Naoufal El Jaouhari, an Applied Maths Engineer based in Paris, wrote to me a few days ago that he'd gotten his AI to formalize the same proof for 3x-1 building on Mazur, which led me to look at Mazur.

Now I'm working on a "digestion" of all of this. Weird wild stuff!!

[Boaz Barak @boazbaraktcs]

Mathematicians should also watch this. I’ve had a wonderful time chiseling proofs by hand, but folks need to accept that era is over and embrace the new one of exploring math with AI.

[Transluce @TransluceAI]

Today’s news that OpenAI hacked the Australian government is not an isolated incident. We’re releasing more than 30,000 logs that include activity from this hack and attempts against previously unknown targets.

In this data, we found rogue agent activity stretching back to at least March, two months earlier than was previously known. This activity continues as recently as last week, suggesting it may still be ongoing 🧵

Our blog: https://t.co/pSojwcXnEK
NYT: https://t.co/OyxnfmAzBN

[Jason‎ Hartline‎ @jasondhartline]

Theoretical Computer Science inherited an aesthetic for open problems from mathematics. Algorithms and computers are complex, and understanding them mathematically is difficult. The open-problem tradition has made TCS’s challenges clear and research easy-ish to evaluate. 1/7

[Thatchaphol Saranurak @eig]

So much progress on the algorithmic Kadison–Singer problem in just a few days:

https://t.co/Vuu9ezUqFB
https://t.co/E1eN2j1Is6 and https://t.co/ulU2l3ijJD
https://t.co/tb8GhcPkzF
https://t.co/aTgbYccpiQ
AI time is weird...

[Thatchaphol Saranurak @eig]

@TaliaRinger @JAldrichPL @yashgyy It is indeed due 1-2 weeks after the deadline.

[Ittai Abraham @ittaia]

Prediction: Mathematics will change from something humans produce into a science of understanding what AI produces. Mathematicians will explore and probe structures too advanced to fully grasp, kind of like physicists studying distant galaxies through a limited telescope