Ben Brubaker (and Rahul Ilango) strikes again! A great article on a mind-bending result!

Quanta Magazine@quantamagazine.org · 3mo ago

Shafi Goldwasser (left), Silvio Micali (right), and Charles Rackoff devised a way to prove that a statement is true without revealing anything about why. www.quantamagazine.org/how-unknowab...

Congratulations to Scott!! It's a good feeling to agree so wholeheartedly with a committee's decision ☺️

Clément Canonne@ccanonne.github.io · 3mo ago

Congratulations to Scott Aaronson, awarded the inaugural Luca Trevisan Award for Expository Work in Theoretical Computer Science "for his sustained and high-impact inspirational efforts to explain and promote our field to broad audiences"! Read the commendation: sigact.org/prizes/trevi... #TCSSky

Learning a lot at the first #FOCS2025 Best Student Paper award, by Rahul Ilango!

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

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...

Simulating Time With Square-Root Space (And With Details) - Ryan Williams

YouTube video by Institute for Advanced Study

youtube.com

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 :)

Marek@marek.onl · last yr.

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.

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.

💡 For students, the yearly IEEE (or ACM) membership costs less than USD 20. And leads to a #FOCS2025 registration fee reduced by USD 80...

This is very impressive. Breaking the sorting barrier for directed single source shortest paths 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

It's fun to publish something 20 years ago which refutes a recently published proof of P ≠ NP

Lance Fortnow@lance.fortnow.com · last yr.

Springer publishes a P ≠ NP "proof" and Eric Allender has words to say. blog.computationalco...

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...

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...

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...

TCS+@tcsplus.bsky.social · last yr.

📢 Our fourth TCS+ talk will be Wednesday, April 23 (10amPT, 1pm ET, 19:00 CEST): Ryan Williams (@rrwilliams.bsky.social), from MIT, will tell us about "Simulating Time With Square-Root Space"! RSVP to receive the link (available one day prior to the talk): forms.gle/hi9pBsgjRBMb... #TCSSky

Ryan's talk is this Wednesday! forms.gle/fZa3ATXC7n14...

TCS+ RSVP: Ryan Williams (2025/05/23)

Title: Simulating Time With Square-Root Space

forms.gle

TCS+@tcsplus.bsky.social · last yr.

📢 Our fourth TCS+ talk will be Wednesday, April 23 (10amPT, 1pm ET, 19:00 CEST): Ryan Williams (@rrwilliams.bsky.social), from MIT, will tell us about "Simulating Time With Square-Root Space"! RSVP to receive the link (available one day prior to the talk): forms.gle/hi9pBsgjRBMb... #TCSSky

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...

when my family asks me about the impact of my research

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 😅

Matthew Sparkes@sparkes.bsky.social · last yr.

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...

I've posted a lightly revised version (mostly revising the discussion at the end) to ECCC eccc.weizmann.ac.il/report/2025/...

Ryan Williams@rrwilliams.bsky.social · last yr.

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!

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

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

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!

DIMACS workshop on fine grained hardness of approximation, July 21-23 Information and registration here, looks interesting! dmac.rutgers.edu/events/detai...

We 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 #OnlineParallels