Sign in

Ryan Williams

@rrwilliams.bsky.social
1.6K followers 183 following 54 posts

professor of EECS at MIT. working in theoretical computer science namely algorithm design, complexity theory, circuit complexity, etc. i'll let you know when P != NP is proved (and when it's not)

PostsRepliesMedia
Ryan Williams @rrwilliams.bsky.social · 20/09/2026
"I believe that the AI revolution will force theoretical research communities to reconsider their nature and re-orient themselves more directly at the centrality of understanding in their endeavor." I certainly hope so. Sadly we can already see people engaging in the potential alternatives
060
Ryan Williams @rrwilliams.bsky.social · 30/06/2026
There's also Q-resolution :) the natural generalization to arbitrary quantified CNFs. Anyway, good name 👍
111
Ryan Williams @rrwilliams.bsky.social · 30/06/2026
I think this is a better name! A sound and complete name, in fact :)
110
Ryan Williams @rrwilliams.bsky.social · 13/05/2026
Ben is on Bluesky here: @benbenbrubaker.bsky.social
040
Ryan Williams @rrwilliams.bsky.social · 13/05/2026
Ben Brubaker (and Rahul Ilango) strikes again! A great article on a mind-bending result!
1172
Ryan Williams @rrwilliams.bsky.social · 09/05/2026
Congratulations to Scott!! It's a good feeling to agree so wholeheartedly with a committee's decision ☺️
0141
Reposted by Ryan Williams
Clément Canonne @ccanonne.github.io · 17/12/2025
Learning a lot at the first #FOCS2025 Best Student Paper award, by Rahul Ilango!
A slide about Charmin and Kirkland toilet paper
1282
Ryan Williams @rrwilliams.bsky.social · 15/12/2025
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 (??)
130
Ryan Williams @rrwilliams.bsky.social · 14/12/2025
Screenshot of ChatGPT running for 1435m 32s
140
Ryan Williams @rrwilliams.bsky.social · 14/12/2025
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
1191
Ryan Williams @rrwilliams.bsky.social · 07/11/2025
Finding new ways to break ChatGPT
Screenshot showing that ChatGPT 5 has been thinking for 3347m and 27s on a prompt
1202
Ryan Williams @rrwilliams.bsky.social · 25/10/2025
🥳🎉👀
030
Ryan Williams @rrwilliams.bsky.social · 24/09/2025
They are doing some construction on the blackboards in the usual classroom, this was the backup
010
Ryan Williams @rrwilliams.bsky.social · 23/09/2025
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...
youtube.com
Simulating Time With Square-Root Space (And With Details) - Ryan Williams
YouTube video by Institute for Advanced Study
1397
Ryan Williams @rrwilliams.bsky.social · 25/08/2025
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 :)
0220
Ryan Williams @rrwilliams.bsky.social · 25/08/2025
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.
020
Reposted by Ryan Williams
Marek @marek.onl · 26/03/2025
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.
2164
Ryan Williams @rrwilliams.bsky.social · 17/08/2025
Is it Bobby Fischer Teaches Chess? en.m.wikipedia.org/wiki/Bobby_F... As a kid, I thought that was such a fun book.
en.m.wikipedia.org
Bobby Fischer Teaches Chess - Wikipedia
040
Reposted by Ryan Williams
FOCS 2026 @focs2026.bsky.social · 08/08/2025
💡 For students, the yearly IEEE (or ACM) membership costs less than USD 20. And leads to a #FOCS2025 registration fee reduced by USD 80...
034
Reposted by Ryan Williams
Suresh Venkatasubramanian @geomblog.bsky.social · 06/08/2025
This is very impressive. Breaking the sorting barrier for directed single source shortest paths search.app/wnEUo
search.app
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.
1205
Ryan Williams @rrwilliams.bsky.social · 05/08/2025
It's fun to publish something 20 years ago which refutes a recently published proof of P ≠ NP
1525
Reposted by Ryan Williams
Lance Fortnow @lance.fortnow.com · 04/08/2025
Springer publishes a P ≠ NP "proof" and Eric Allender has words to say. blog.computationalco...
blog.computationalcomplexity.org
Some thoughts on journals, refereeing, and the P vs NP problem
A guest post by Eric Allender prompted by an  (incorrect) P ≠ NP proof   recently published  in Springer Nature's Frontiers of Computer Scie...
64415
Reposted by Ryan Williams
Tom Gur @tomgur.bsky.social · 19/07/2025
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...
arxiv.org
0303
Ryan Williams @rrwilliams.bsky.social · 26/06/2025
There is session 9C... But yeah not a lot of papers
120
Reposted by Ryan Williams
Ryan O'Donnell @booleananalysis.bsky.social · 09/06/2025
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.)
cs.unibocconi.eu
14617
Ryan Williams @rrwilliams.bsky.social · 11/06/2025
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...
computationalcomplexity.org
Computational Complexity Conference
040
Reposted by Ryan Williams
Lance Fortnow @lance.fortnow.com · 07/06/2025
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...
0337
Ryan Williams @rrwilliams.bsky.social · 04/05/2025
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...
000
Ryan Williams @rrwilliams.bsky.social · 04/05/2025
ChatGPT 4o thinks 27 < 10
1120
Reposted by Ryan Williams
Michael Nielsen @michaelnielsen.bsky.social · 25/04/2025
One strange thing about writing is that the harder you work, the easier many people think it was to do
3502
Reposted by Ryan Williams
TCS+ @tcsplus.bsky.social · 23/04/2025
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...
tcsplus.org
TCS+ - Next TCS+ talk
Our fourth TCS+ talk of the season will take place on April 23 (10:00am Pacific Time, 1:00 pm Eastern Time, 19:00 Central European Summer Time, 17:00 UTC — check yours here). Ryan Williams, from MIT, ...
062
Reposted by Ryan Williams
TCS+ @tcsplus.bsky.social · 21/04/2025
Ryan's talk is this Wednesday! forms.gle/fZa3ATXC7n14...
forms.gle
TCS+ RSVP: Ryan Williams (2025/05/23)
Title: Simulating Time With Square-Root Space
084
Ryan Williams @rrwilliams.bsky.social · 11/04/2025
If you take a photo of your whiteboard with the camscanner app, it will also do this
010
Reposted by Ryan Williams
Josh Alman @jalman.bsky.social · 23/03/2025
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...
theory day website
0154
Ryan Williams @rrwilliams.bsky.social · 02/04/2025
Cool. Just taught Rice's theorem yesterday!
010
Ryan Williams @rrwilliams.bsky.social · 01/04/2025
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!
020
Ryan Williams @rrwilliams.bsky.social · 06/03/2025
👀 ...
010
Reposted by Ryan Williams
Greg Bodwin @gbodwin.bsky.social · 04/03/2025
when my family asks me about the impact of my research
14813
Ryan Williams @rrwilliams.bsky.social · 03/03/2025
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...
020
Ryan Williams @rrwilliams.bsky.social · 03/03/2025
If this problem is in n^{0.99} space, then the simulation of time in small space can be improved beyond a square root
010
Ryan Williams @rrwilliams.bsky.social · 03/03/2025
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...
drops.dagstuhl.de
Easiness Amplification and Uniform Circuit Lower Bounds
121
Reposted by Ryan Williams
FOCS 2026 @focs2026.bsky.social · 02/03/2025
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
sigact.org
ACM SIGACT - Knuth Prize
0105
Ryan Williams @rrwilliams.bsky.social · 01/03/2025
The STOC 2025 Theory Fest is looking for workshop proposals! Apply here: stoc2025theoryfest.netlify.app Deadline is March 9th, so act fast!
stoc2025theoryfest.netlify.app
Vite + React + TS
072
Ryan Williams @rrwilliams.bsky.social · 28/02/2025
Useless? Hmpf... Could someone send a link without the paywall? I'd like to read about what else I said 😅
2131
Ryan Williams @rrwilliams.bsky.social · 28/02/2025
I tried to made the same joke on Scott Aaronson's blog, but nobody else seemed to get it :)
110
Ryan Williams @rrwilliams.bsky.social · 28/02/2025
Thanks! I'll visit IAS soon for a few days to talk about it
010
Ryan Williams @rrwilliams.bsky.social · 26/02/2025
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.
010
Ryan Williams @rrwilliams.bsky.social · 25/02/2025
I have no idea if the simulation can be improved further (if that's what you mean)
020
Ryan Williams @rrwilliams.bsky.social · 24/02/2025
I've posted a lightly revised version (mostly revising the discussion at the end) to ECCC eccc.weizmann.ac.il/report/2025/...
eccc.weizmann.ac.il
ECCC - TR25-017
2205
Ryan Williams @rrwilliams.bsky.social · 23/02/2025
Thanks. I'd be surprised if there was no way to extend it to RAMs. I think the warmup theorem in the paper happens to be an easy way to see that space saving is possible.
010