Computational Complexity

In fall of 1985 when I started graduate school, my advisor Michael Sipser asked me to read an early handwritten manuscript by Johan Håstad of his switching lemma.

So what to make of OpenAI and the future of Math?

In the OpenAI Math Drop some papers have Lean proofs, others don't, including L = RL = BPL.

Lance blogged on the OpenAI solutions to many problems here and also created a website of the TCS-related problems OpenAI claims to have solved here.

I wrote the post below last week.

(This was written about 9 months ago.

I got the following question in an email.

The STOC conference (and likely others) are requiring that a submission says how much AI was used.

The 59th ACM Symposium on the Theory of Computing takes place in Atlanta next June, part of the Federated Computing Research Conference.

The following conversation is fictional. --------------------------- ALICE: (Looking over a student's record.)

ITMS 2026 Two years ago I attended the International Manufacturing Technology Show in Chicago's McCormick Place and found a rather limited focus on artificial intelligence among the exhibitors.

On September 1, 2026: LANCE: I'm surprised you haven't blogged about OpenAI solving 10 open math problems.

I was working on this week's post on Lean after reading Kevin Hartnett's book The Proof in the Code: How a Truth Machine Is Transforming Math and AI.

Richard Stearns (right) and Juris Hartmanis in May 1963.

Ben Brubaker has a new Quanta essay Does Computer Science Need Computers?

BILL: Lance, I have a question and a meta question: a) List all the presidents and vice presidents who were colorblind. b) Do you know this sort of thing since you are colorblind, and hence might have looked this up in the past?

There's a scene in Apollo 13 where Jim Lovell, played by Tom Hanks, asks Houston control to check his calculations, which they do using a slide rule.

In the past, new PhD students would ask how they could succeed when they had to compete with the likes of say, Richard Karp or Avi Wigderson.

Lance has posted about his, and around 160 others, being laid off from IIT here.

Enjoying Idaho while ignoring Illinois Today is the first day of my life that I am unemployed.

(Some of this came from a Reddit post I read, and some of the comments on it.)

I was watching a Jeopardy from 2004 (The Game Show Channel is rerunning Ken Jennings streak) and the following question raises a good question.

Let's say there is a statement in math T that you wonder whether it's true or false.

Back in the 90s when I was a young professor at the University of Chicago, we would have a Complexity Class of the Week where I would take some interesting complexity class, write down on a white board everything we knew about it with some open problems a…

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf.

Herman Chernoff passed away on July 6, 5 days after turning 103.

The excellent graphic novel Prime Suspects: The Anatomy of Integers and Permutations by Andrew Granville and Jennifer Granville, illustrated by Robert J Lewis, (I wrote a review of this graphic novel, for SIGACT News, here.) has an appendix, which is not…

Two editorials in the July issue of the Communications of the Association for Computing Machinery ask about the decay and future of the organization itself.

I recently read Alan Alda's first memoir Never have your dog stuffed which was pretty good.

Harry Lewis pointed Bill and me to Gottfried Leibniz's 1677 treatise The True Method (translated from the original French).

Peter Brass is a prior NSF theory director.

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time.

(All references in this blog post can be found in the main article the post is about which is here.)

Last week I saw a talk by Northwestern professor Nina Wieda on the history of the Silk Road, a network of trading routes across Asia active from the second century BCE until the mid-15th century.

A mnemonic device is a sentence where the first letters of the words are helpful to remember something.

There are two ways to look at the P v NP problem, as a formal mathematically defined conjecture as a Clay Millennium Prize Problem, and as the more intuitive notion that everything efficiently verifiable is efficiently computable and the implications that…

(In 2008 I wrote a survey of some of the known sum-product theorems, see here.