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/2026There's also Q-resolution :) the natural generalization to arbitrary quantified CNFs. Anyway, good name 👍 111
Ryan Williams @rrwilliams.bsky.social · 30/06/2026I think this is a better name! A sound and complete name, in fact :) 110
Ryan Williams @rrwilliams.bsky.social · 13/05/2026Ben is on Bluesky here: @benbenbrubaker.bsky.social 040
Ryan Williams @rrwilliams.bsky.social · 13/05/2026Ben Brubaker (and Rahul Ilango) strikes again! A great article on a mind-bending result! 1172
Ryan Williams @rrwilliams.bsky.social · 09/05/2026Congratulations to Scott!! It's a good feeling to agree so wholeheartedly with a committee's decision ☺️ 0141
Reposted by Ryan WilliamsClément Canonne @ccanonne.github.io · 17/12/2025Learning a lot at the first #FOCS2025 Best Student Paper award, by Rahul Ilango! 1282
Ryan Williams @rrwilliams.bsky.social · 15/12/2025I 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/2025studying 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 · 24/09/2025They are doing some construction on the blackboards in the usual classroom, this was the backup 010
Ryan Williams @rrwilliams.bsky.social · 23/09/2025Today 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.comSimulating Time With Square-Root Space (And With Details) - Ryan WilliamsYouTube video by Institute for Advanced Study 1397
Ryan Williams @rrwilliams.bsky.social · 25/08/2025A 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/2025Nowadays, 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 WilliamsMarek @marek.onl · 26/03/2025Adi 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/2025Is 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.orgBobby Fischer Teaches Chess - Wikipedia 040
Reposted by Ryan WilliamsFOCS 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 WilliamsSuresh Venkatasubramanian @geomblog.bsky.social · 06/08/2025This is very impressive. Breaking the sorting barrier for directed single source shortest paths search.app/wnEUosearch.appNew Method Is the Fastest Way To Find the Best Routes | Quanta MagazineA 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/2025It's fun to publish something 20 years ago which refutes a recently published proof of P ≠ NP 1525
Reposted by Ryan WilliamsLance Fortnow @lance.fortnow.com · 04/08/2025Springer publishes a P ≠ NP "proof" and Eric Allender has words to say. blog.computationalco...blog.computationalcomplexity.orgSome 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 WilliamsTom Gur @tomgur.bsky.social · 19/07/2025Hirahara, 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/2025There is session 9C... But yeah not a lot of papers 120
Reposted by Ryan WilliamsRyan O'Donnell @booleananalysis.bsky.social · 09/06/2025Spread 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/2025CCC’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 WilliamsLance Fortnow @lance.fortnow.com · 07/06/2025The 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/2025Yeah 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
Reposted by Ryan WilliamsMichael Nielsen @michaelnielsen.bsky.social · 25/04/2025One strange thing about writing is that the harder you work, the easier many people think it was to do 3502
Reposted by Ryan WilliamsTCS+ @tcsplus.bsky.social · 23/04/2025The 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.orgTCS+ - Next TCS+ talkOur 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 WilliamsTCS+ @tcsplus.bsky.social · 21/04/2025Ryan's talk is this Wednesday! forms.gle/fZa3ATXC7n14...forms.gleTCS+ RSVP: Ryan Williams (2025/05/23)Title: Simulating Time With Square-Root Space 084
Ryan Williams @rrwilliams.bsky.social · 11/04/2025If you take a photo of your whiteboard with the camscanner app, it will also do this 010
Reposted by Ryan WilliamsJosh Alman @jalman.bsky.social · 23/03/2025NY 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... 0154
Ryan Williams @rrwilliams.bsky.social · 01/04/2025I 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
Reposted by Ryan WilliamsGreg Bodwin @gbodwin.bsky.social · 04/03/2025when my family asks me about the impact of my research 14813
Ryan Williams @rrwilliams.bsky.social · 03/03/2025Well, 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/2025If 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/2025I 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.deEasiness Amplification and Uniform Circuit Lower Bounds 121
Reposted by Ryan WilliamsFOCS 2026 @focs2026.bsky.social · 02/03/2025Please 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... #TCSSkysigact.orgACM SIGACT - Knuth Prize 0105
Ryan Williams @rrwilliams.bsky.social · 01/03/2025The STOC 2025 Theory Fest is looking for workshop proposals! Apply here: stoc2025theoryfest.netlify.app Deadline is March 9th, so act fast!stoc2025theoryfest.netlify.appVite + React + TS 072
Ryan Williams @rrwilliams.bsky.social · 28/02/2025Useless? 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/2025I 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/2025Thanks! I'll visit IAS soon for a few days to talk about it 010
Ryan Williams @rrwilliams.bsky.social · 26/02/2025Not 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/2025I have no idea if the simulation can be improved further (if that's what you mean) 020
Ryan Williams @rrwilliams.bsky.social · 24/02/2025I've posted a lightly revised version (mostly revising the discussion at the end) to ECCC eccc.weizmann.ac.il/report/2025/...eccc.weizmann.ac.ilECCC - TR25-017 2205
Ryan Williams @rrwilliams.bsky.social · 23/02/2025Thanks. 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