Ryan Williams

A slide about Charmin and Kirkland toilet paper

Learning a lot at the first #FOCS2025 Best Student Paper award, by Rahul Ilango!

I am soo nice.. my system instructions include "please" and "good luck, we believe in you, but you should also believe in yourself!" ☺️ I learned the latter trick from Javier Gomez-Serrano, it seems being nice helps them do math (??)

Screenshot of ChatGPT running for 1435m 32s

studying chatgpt's busy beaver number: how long can it run and still halt. finished one prompt in slightly under 24 hrs. the response was just as unhinged as a human would sound after grinding that long

Screenshot showing that ChatGPT 5 has been thinking for 3347m and 27s on a prompt

Finding new ways to break ChatGPT

🥳🎉👀

They are doing some construction on the blackboards in the usual classroom, this was the backup

YouTube video by Institute for Advanced Study Simulating Time With Square-Root Space (And With Details) - Ryan Williams

Today at IAS, I gave a 2 hr 15 mins lecture on why TIME[t] is in SPACE[√(t log t)]. You can watch it here!
www.youtube.com/watch?v=ThLv...

A related anecdote: as a PhD student, I was assigned to be a teaching assistant for my advisor's cryptography course. When I asked Manuel how I should prepare for this, he replied:

"Read every paper that Adi Shamir has written."

I tried to follow this advice. At least I read the abstracts :)

Nowadays, I think that slightly biasing your reading priority towards the top conferences/venues in your area makes sense. But I still believe that attempting to read every abstract in your area is good advice.

Adi Shamir's advice to young researchers:

1. Read, read, read. Back in the eighties, I read every cryptography paper out there. Once that became impossible, I read the abstract of every paper. Now I read at least every title.

Bobby Fischer Teaches Chess - Wikipedia

Is it Bobby Fischer Teaches Chess?
en.m.wikipedia.org/wiki/Bobby_F...
As a kid, I thought that was such a fun book.

💡 For students, the yearly IEEE (or ACM) membership costs less than USD 20. And leads to a #FOCS2025 registration fee reduced by USD 80...

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

It's fun to publish something 20 years ago which refutes a recently published proof of P ≠ NP

Springer publishes a P ≠ NP "proof" and Eric Allender has words to say.

blog.computationalco...

Hirahara, Illango, and Loff posted on the arXiv a lovely result, showing that determining the communication complexity of a function f is NP-hard. A fundamental question first asked by Yao in '79. The proof is very clean and elegant. A fun read for the weekend!

arxiv.org/pdf/2507.104...

There is session 9C... But yeah not a lot of papers

Spread the word: there is a new prize in Theoretical Computer Science in honor of Luca Trevisan--

cs.unibocconi.eu/call-nominat...

(Intent-to-nominate letters due by July 31.)

CCC’25 will take place August 5-8 at the Fields Institute in Toronto! Students/postdocs (from any institution) are eligible to apply for a travel allowance. For full consideration, please apply by June 20; awards to be announced on June 25. www.computationalcomplexity.org/travelAllowa...

The 2025 Gödel Prize is given to Eshan Chattopadhyay and David Zuckerman, “Explicit two-source extractors and resilient functions”.

Paper: doi.org/10.4007/anna...

Favorite Theorems Blog Post: blog.computationalco...

Yeah GP and I were arguing over this 😂 Eventually he believed my side, and proved it true by induction. We wanted to check what ChatGPT thought...

ChatGPT 4o thinks 27 < 10

One strange thing about writing is that the harder you work, the easier many people think it was to do

The link for Ryan Williams' talk (@rrwilliams.bsky.social) is now available on our website.

See you tomorrow, 1pm ET! www.tcsplus.org/welcome/next...

Ryan's talk is this Wednesday!

forms.gle/fZa3ATXC7n14...

If you take a photo of your whiteboard with the camscanner app, it will also do this

theory day website

NY Theory Day is returning on Friday April 11 at Columbia! It's free to attend but you have to register on the website by April 4. We have a great speaker lineup:

Rachel Cummings (Columbia)
Bill Kuszmaul (CMU)
Nick Spooner (Cornell)
Ryan Williams (MIT)

sites.google.com/view/nyctheo...

Cool. Just taught Rice's theorem yesterday!

I can say for sure that this result has totally broken my intuition about what are "reasonable" time-space tradeoff lower bounds that we can assume for time-bounded computation!