Since today Bipartite Perfect Matching is in NC. The proof uses connections between coding theory and Hall's theorem. Presented at WACT 2026. Yay!!!

The 2026 Gödel Prize is awarded to Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart for Robust Estimators in High Dimensions without the Computational Intractability Paper: doi.org/10.1137/17M1... Citation: www.sigact.org/prize...

There's a tendency in the popular press to use the age of an open problem as a proxy for hardness. The Erdos unit-distance problem dates to 1946, 25 years before Cook and Levin wrote about P v NP. Does that mean that P v NP is an easier problem? No.

As US science funding becomes more limited, more bureaucratic, more political, we turn more to industry and foundations to help fund and set our research agenda. And now we have to deal with the consequences. My thoughts on yesterday's State of the Sciences Address:

Leiden Declaration on AI and Math leidendeclaration.ai/ NYT Story www.nytimes.com/2026... I generally support the declaration, particularly the concerns about a tiered systems based on who has access to the latest models.

It's time for the Theory Jobs spreadsheet for 2026! The theory CS community crowdsources who accepted which jobs every year. Blog post: kamathematics.wordpress.com/2026/06/01/t... Form: docs.google.com/forms/d/1Qcn... Results: docs.google.com/spreadsheets...

Bill talks about the tales of Alice, Bob and Carol as they figure out who should get the research credit.

“The sum-product conjecture is false for real numbers” THOMAS F. BLOOM, WILL SAWIN, CARL SCHILDKRAUT, AND DMITRII ZHELEZOV A human proof that exploits the same kind of “tower of fields” that was used in the AI-generated counterexample to the unit-distance conjecture!

The recent AI proof of the Erdős Unit Distance Problem brings up challenging questions about paper authorship now and into the future.

Congratulations to Tal Rabin, Shubhangi Saraf, and Lisa Zhang, recognized by the SIGACT Distinguished Service Award for their role in making Theoretical Computer Science more welcoming and inclusive with the Women In Theory (WIT) workshop! sigact.org/prizes/servi... (via @gautamkamath.com)

Let's not forget the real person who inspired the recent AI proofs, Paul Erdős. I was lucky to see him lecture while a grad student. In 2013, we celebrated his centenary. blog.computationalco... And I highly recommend Paul Hoffman's biography "The Man Who Loved Only Numbers".

Encyclical Letter Magnifica Humanitas of His Holiness Pope Leo XIV on Safeguarding the Human Person in the Time of Artificial Intelligence www.vatican.va/conte... NYT article: www.nytimes.com/2026...

Bill tells the tale of two Erdős distance problems, one solved by humans and the other by machine.

Can we flip the script so that AI creates interesting open math problems for humans to work on?

Gil Kalai on the new AI proof of the Erdős unit distance problem

How hard is it to avoid the range of a function? The problem that captures probabilistic constructions, Kolmogorov complexity, circuit complexity, and so much more.

Accepted papers for 2026 Computational Complexity Conference computationalcomplex... I had AI search for links--found 30 of 43. docs.google.com/docu...

Bill gets award confusion.

Our blog covered prediction markets twenty years ago, but now that real money is involved, everything changes.

STOC TheoryFest will feature a "Can AI do Theory?" workshop including some impressive speakers and a poster session. pritishkamath.github...

Scott Aronson wins the first inaugural Luca Trevisan Award for Expository Work sigact.org/prizes/tr... There's always next year.

Bill tries to find a book on Amazon. He can't find it until he uses Google.

One challenge we have as the complexity blog of record: When do we actually know when someone has passed away?

Bill has more to say about Michael Rabin

Machine learning works so well because it doesn't have to.

TIL the Riemann Hypothesis is equivalent to the statement that the number of primes up to x additively differs from the integral of 1/ln(x) by at most O(√x log x). This is so much easier to understand than the zeros of the zeta function.

Bernard Sufrin was looking for a student to create a Logic Engine for Argument by Pointing. We gave him Claude. LEAP: leap-y2r7.onrender.com/ GitHub: github.com/fortnow/l... Blog Post: blog.computationalco...

In the announcement of ChatGPT 5.5, they mentioned a new Ramsey theorem proved by the system. cdn.openai.com/pdf/6... I asked my Ramsey expert, Bill Gasarch, and he asked ChatGPT who found it interesting. But the reason ChatGPT found it interesting was not interesting to Bill.

Bill Gasarch remembers Turing laureate Michael Rabin who passed away last week.

Martin Ljungqvist wrote a Swedish police thriller, recently translated into English, where P v NP takes center stage. sagaegmont.publica.l....

A new journal is offering $600 for authors who publish with them in order to build up a reputation so they can charge authors later. www.innovationforeve... Under no circumstances should you send them your AI slop papers.

An overview of my research on how machine learning handles complex behavior. We abstract machine learning using computational complexity, and show how such models use randomness to handle what they can't directly compute.

Hampshire college has 17 MPH speed limits for reasons only math nerds would know. And now Hampshire is no more. www.hampshire.edu/ne... www.nytimes.com/2026... 1/2

Ask questions to the ACM Presidential candidates, Jens Palsberg and Elisa Bertino. www.cs.rice.edu/~var... And don't forget to vote if you are an ACM member.

Former NSF theory program director Peter Brass guest posts on the state of the foundation.

Today is World Quantum Day where we celebrate all the amazingly useful things quantum computing has done for us. Well, there's always next year.

I knew that opera companies use television screens so the singers can follow the conductor without having to look in the pit. What I didn't know is that they use analog TVs because digital has too much lag.

What, Bill didn't really talk to the pope about loaves and fishes? I feel fooled. And also honored to have the same initials as Loaves and Fishes.

My new paper taking a computational complexity lens to machine learning. arxiv.org/abs/2604.0... We abstract ML models as non-uniformly efficiently computable distributions and show that learning computable distributions forces the use of probability to manage complexity.

My very first memories were of watching the moon landing on a TV in my grandmother's apartment. So its feels a bit weird that 57 years later we are getting so excited by just flying around it.

Here are the solutions to my problems from last week blog.computationalco... The original problems in case you want to try them first

With Easter coming up, Bill helps the pope solve one of Christianity's greatest mysteries.

Our president just signed an executive order stating that the Cook-Levin theorem will now be known as the Trump-Cook-Levin theorem. I'd better go revise my grant application.

A few fun problems in theory to chew on.

My time in Oxford is, alas, coming ot an end. Some reflections.

Scammers be aware: Bill tells you how much you get can off of him.

I'm working on a paper and saying for details on the preliminaries, consult these textbooks. But they are better off going to a good chatbot. Before they could have gone to Wikipedia. But I will still point to the textbooks because that's how we play the game.

The German mathematician Gerd Faltings is the winner of this year's Abel Prize, an honor that is regarded as mathematics’ version of the Nobel Prize. He proved a conjecture that had been unsolved for six decades, using connections between numbers and geometry.

My blog post on the Bennett-Brassard Turing Award.

Charlie Bennett and Gilles Brassard win the Turing Award for Quantum Information Science. Most notably they developed the theory for a provably secure quantum key distribution protocol. awards.acm.org/about...