Ryan Williams

💡 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

The STOC 2025 Theory Fest is looking for workshop proposals!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!

Useless? Hmpf...

Could someone send a link without the paywall?
I'd like to read about what else I said 😅

I tried to made the same joke on Scott Aaronson's blog, but nobody else seemed to get it :)

Thanks! I'll visit IAS soon for a few days to talk about it

Not silly! I think in that case the space bound would be O(sqrt(t log t)) (square rooting the t log t running time of the oblivious simulation), the space bound of the main result.

I have no idea if the simulation can be improved further (if that's what you mean)