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

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

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

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

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

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

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

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

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 😅

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

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

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

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

Check out ITCS 2025. I look forward to attending in person! itcs-conf.org/itcs25/itcs2...

Hi everyone! I'm looking forward to hanging out in this new space :) Expect sporadic complexity-theoretic updates and dad humor