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 · 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 1201
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
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
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
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 14718
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... 0348
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
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
Reposted by Ryan WilliamsGreg Bodwin @gbodwin.bsky.social · 04/03/2025when my family asks me about the impact of my research 14913
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 😅 2141
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 2215
Reposted by Ryan WilliamsQuanta Magazine @quantamagazine.org · 21/02/2025Adding full storage space can in principle make computers more powerful. This idea is at the very heart of catalytic computing, a burgeoning theoretical framework. buff.ly/4i6G7Tzbuff.lyCatalytic Computing Taps the Full Power of a Full Hard Drive | Quanta MagazineTen years ago, researchers proved that adding full memory can theoretically aid computation. They’re just now beginning to understand the implications. 0367
Ryan Williams @rrwilliams.bsky.social · 21/02/2025New 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 1726475
Ryan Williams @rrwilliams.bsky.social · 09/02/2025DIMACS workshop on fine grained hardness of approximation, July 21-23 Information and registration here, looks interesting! dmac.rutgers.edu/events/detai...dmac.rutgers.eduDIMACS :: Details 0114
Reposted by Ryan WilliamsOnline Parallels (mastodon @onlineparallels) @onlineparallels.bsky.social · 17/12/2024We are launching an 𝐮𝐧𝐨𝐟𝐟𝐢𝐜𝐢𝐚𝐥 and experimental online parallel event for the conference ITCS25, aimed at everyone who cannot attend the conference in person for whatever reasons. (1/2) sites.google.com/view/itcs202... #ITCS25 #ITCS2025 #OnlineParallelssites.google.comITCS'25 online parallelWhat we do Welcome! This site is about an online parallel event for the conference ITCS'25 that aims to provide an inclusive platform for the TCS researchers unable to attend the conference in person.... 1228
Ryan Williams @rrwilliams.bsky.social · 22/11/2024I recently gave a general CS lecture at the University of Washington on some long-running threads in my research. Hope you enjoy! www.youtube.com/watch?v=qQZL...youtube.comA Dogged Pursuit For Satisfaction–Ryan Williams (MIT CSAIL)YouTube video by Paul G. Allen School 1313
Reposted by Ryan Williamsdreichman.bsky.social @dreichman.bsky.social · 22/11/2024Check out ITCS 2025. I look forward to attending in person! itcs-conf.org/itcs25/itcs2... 042
Ryan Williams @rrwilliams.bsky.social · 15/11/2024Hi everyone! I'm looking forward to hanging out in this new space :) Expect sporadic complexity-theoretic updates and dad humor 2430