Ryan Williams

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!

👀 ...

when my family asks me about the impact of my research

Well, linear programming is P complete (e.g., it can efficiently implement circuit evaluation), and the current wisdom is that such problems should not be in n^{eps} space for all eps > 0...

If this problem is in n^{0.99} space, then the simulation of time in small space can be improved beyond a square root

I would have said the Circuit Evaluation problem, but now we know better ... :)

A "conplete" problem for n^2 time would be something like "General Circuit n-Composition" problem defined in the paper
drops.dagstuhl.de/entities/doc...

Please nominate candidates to the 🏆 Knuth Prize, to be awarded this year during #STOC2025!

The prize recognizes "major research accomplishments and contributions to the foundations of Computer Science over an extended period of time."

⏰ Deadline: March 31

www.sigact.org/prizes/knuth... #TCSSky