Ryan Williams
@rrwilliams.bsky.social
professor of EECS at MIT, currently visiting IAS. 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)
i'll let you know when P != NP is proved (and when it's not)
Finding new ways to break ChatGPT
November 7, 2025 at 12:14 AM
Finding new ways to break ChatGPT
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...
www.youtube.com/watch?v=ThLv...
Simulating Time With Square-Root Space (And With Details) - Ryan Williams
YouTube video by Institute for Advanced Study
www.youtube.com
September 23, 2025 at 8:22 PM
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...
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 :)
"Read every paper that Adi Shamir has written."
I tried to follow this advice. At least I read the abstracts :)
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.
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.
August 25, 2025 at 5:46 PM
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 :)
"Read every paper that Adi Shamir has written."
I tried to follow this advice. At least I read the abstracts :)
Reposted by Ryan Williams
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.
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.
March 26, 2025 at 11:24 AM
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.
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.
Reposted by 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...
August 8, 2025 at 12:43 AM
💡 For students, the yearly IEEE (or ACM) membership costs less than USD 20. And leads to a #FOCS2025 registration fee reduced by USD 80...
Reposted by Ryan Williams
This is very impressive. Breaking the sorting barrier for directed single source shortest paths
search.app/wnEUo
search.app/wnEUo
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.
search.app
August 6, 2025 at 5:33 PM
This is very impressive. Breaking the sorting barrier for directed single source shortest paths
search.app/wnEUo
search.app/wnEUo
It's fun to publish something 20 years ago which refutes a recently published proof of P ≠ NP
August 5, 2025 at 4:44 AM
It's fun to publish something 20 years ago which refutes a recently published proof of P ≠ NP
Reposted by Ryan Williams
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/pdf/2507.104...
arxiv.org
July 19, 2025 at 11:28 AM
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/pdf/2507.104...
Reposted by Ryan Williams
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/call-nominat...
(Intent-to-nominate letters due by July 31.)
cs.unibocconi.eu
June 9, 2025 at 12:46 PM
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/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...
Computational Complexity Conference
www.computationalcomplexity.org
June 11, 2025 at 9:03 PM
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...
Reposted by Ryan Williams
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...
Paper: doi.org/10.4007/anna...
Favorite Theorems Blog Post: blog.computationalco...
June 7, 2025 at 10:59 PM
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...
Paper: doi.org/10.4007/anna...
Favorite Theorems Blog Post: blog.computationalco...
ChatGPT 4o thinks 27 < 10
May 4, 2025 at 3:52 PM
ChatGPT 4o thinks 27 < 10
Reposted by Ryan Williams
One strange thing about writing is that the harder you work, the easier many people think it was to do
April 25, 2025 at 4:47 AM
One strange thing about writing is that the harder you work, the easier many people think it was to do
Reposted by Ryan Williams
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...
See you tomorrow, 1pm ET! www.tcsplus.org/welcome/next...
April 23, 2025 at 12:24 AM
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...
See you tomorrow, 1pm ET! www.tcsplus.org/welcome/next...
Reposted by Ryan Williams
April 21, 2025 at 9:01 AM
Reposted by Ryan Williams
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...
Rachel Cummings (Columbia)
Bill Kuszmaul (CMU)
Nick Spooner (Cornell)
Ryan Williams (MIT)
sites.google.com/view/nyctheo...
March 23, 2025 at 9:32 PM
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...
Rachel Cummings (Columbia)
Bill Kuszmaul (CMU)
Nick Spooner (Cornell)
Ryan Williams (MIT)
sites.google.com/view/nyctheo...
Reposted by Ryan Williams
when my family asks me about the impact of my research
March 4, 2025 at 5:34 PM
when my family asks me about the impact of my research
Reposted by Ryan Williams
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 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
ACM SIGACT - Knuth Prize
www.sigact.org
March 2, 2025 at 1:37 AM
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 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!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!
Vite + React + TS
stoc2025theoryfest.netlify.app
March 1, 2025 at 3:06 PM
The STOC 2025 Theory Fest is looking for workshop proposals!
Apply here:
stoc2025theoryfest.netlify.app
Deadline is March 9th, so act fast!
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 😅
Could someone send a link without the paywall?
I'd like to read about what else I said 😅
A shocking discovery about the relationship between memory and time in computation has wowed computer scientists.
“It kind of shakes my world view,” says @rrwilliams.bsky.social. “I’m still just shocked it even exists.”
Unfortunately it's probably useless.
www.newscientist.com/article/2469...
“It kind of shakes my world view,” says @rrwilliams.bsky.social. “I’m still just shocked it even exists.”
Unfortunately it's probably useless.
www.newscientist.com/article/2469...
Shock discovery tears up the rules of time and space inside a computer
Time and memory space are the two main constraints on what we can compute, and understanding their relationship is a key part of computational complexity research
www.newscientist.com
February 28, 2025 at 4:23 PM
Useless? Hmpf...
Could someone send a link without the paywall?
I'd like to read about what else I said 😅
Could someone send a link without the paywall?
I'd like to read about what else I said 😅
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/report/2025/...
February 24, 2025 at 11:42 AM
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/report/2025/...
Reposted by Ryan Williams
Adding full storage space can in principle make computers more powerful. This idea is at the very heart of catalytic computing, a burgeoning theoretical framework.
https://buff.ly/4i6G7Tz
https://buff.ly/4i6G7Tz
Catalytic Computing Taps the Full Power of a Full Hard Drive | Quanta Magazine
Ten years ago, researchers proved that adding full memory can theoretically aid computation. They’re just now beginning to understand the implications.
buff.ly
February 21, 2025 at 9:04 PM
Adding full storage space can in principle make computers more powerful. This idea is at the very heart of catalytic computing, a burgeoning theoretical framework.
https://buff.ly/4i6G7Tz
https://buff.ly/4i6G7Tz
New paper: Simulating Time With Square-Root Space
people.csail.mit.edu/rrw/time-vs-...
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
people.csail.mit.edu/rrw/time-vs-...
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
people.csail.mit.edu
February 21, 2025 at 10:19 PM
New paper: Simulating Time With Square-Root Space
people.csail.mit.edu/rrw/time-vs-...
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
people.csail.mit.edu/rrw/time-vs-...
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
DIMACS workshop on fine grained hardness of approximation, July 21-23
Information and registration here, looks interesting!
dmac.rutgers.edu/events/detai...
Information and registration here, looks interesting!
dmac.rutgers.edu/events/detai...
DIMACS :: Details
dmac.rutgers.edu
February 9, 2025 at 6:20 PM
DIMACS workshop on fine grained hardness of approximation, July 21-23
Information and registration here, looks interesting!
dmac.rutgers.edu/events/detai...
Information and registration here, looks interesting!
dmac.rutgers.edu/events/detai...