Lance Fortnow

My occasional reminder that the solution to P v NP is not around the corner. The claimed refutation to ETH doesn't reduce the running times of NP problems in general, such as 3-coloring or CNF-SAT with no bounds on the clause size. We still have no approach to settling P v NP.

Bill looks at algorithms that are probably not optimal.

Bill and I revive the vidcast to talk about the current moment. Enjoy!

One of my readers calls me out on a prediction I made that I could be replaced as a teacher. blog.computationalco... Clip: share.gemini.google/...

Ruixiang Zhang told me about MathHelm, a non-profit site from mathematicians for mathematicians to discuss AI generated math papers.

Interesting Precedence: In 1989 the AMS published a paper "Short proofs of two hypergeometric summation formulas of Karlsson" authored by Shalosh B. Ekhad, the nom de computer of Doron Zeilberger. doi.org/10.1090/S000... HT Evangelos Georgiadis

Noam Nisan once said to me that it is better to read a poorly written proof because you'll come out of it with a better understand than if the proof is well written. Now you get your chance.

If you write a paper and AI is the main driver of the proof, that should go on the first page, mentioned in the abstract or as a footnote in the title and not just buried at the end of the paper. Otherwise you are claiming research that is not quite your own.

Avi Wigderson surveys the recently departed Michael Rabin's research

Bill's thoughts on AI and Math

I asked Claude to summarize mathematicians reactions to October 6th github.com/fortnow/A...

So why is it so hard to formalize computational complexity? it's not the hard stuff, but showing algorithms actually sit in polynomial time.

By request, a Claude rewrite of the Perfect-completeness 2-1 Games Theorem.

Moni Naor wins the 2026 Knuth Prize, the highest career award in theoretical computer science. www.sigact.org/Prize...

NYT Daily interviews Steven Strogatz on AI and Mathematics. www.nytimes.com/2026... No spoilers but it takes an unexpected turn about 24 minutes in.

Bill posts on his favorite of the OpenAI theorems.

Don’t panic! Nobody knows what mathematics will look like on the other side and it will take us time to figure it out. Wait it out and don’t change your plans. For now choose one of the new results and try to understand the proof. You might learn something new and interesting.

While OpenAI is better (for now) at mathematical proofs, Claude does a better job writing up mathematics. So I had Claude write a new version of the Unique Games paper.

The existential threat from artificial intelligence is not that it will kill us all but that it will take away our relevance.

Some initial thoughts on OpenAI's incredible paper drop (UGC, ω ≤ 9/4, L = BPL) and some earlier AI-assisted work on my open problems. blog.computationalco... And a website to make it a little easier to browse OpenAI's TCS-related results lance.fortnow.com/op...

arxiv.org/abs/2610.06783

Bill looks at jobs that help create data to train AI. Sounds like all our jobs right now.

A few news items: Trump held back about a fifth of the NSF budget www.nytimes.com/2026... arXiv to limit submitters to two submissions per month blog.arxiv.org/2026/...

Registration for #FOCS2026 is now open: focs.computer.org/2026/registr... Early bird deadline: ⏰ October 26, AoE

A reader asks whether programming will help understand why there are still some problems that even the most powerful computers struggle to handle efficiently.

If I have seen farther, it is by standing on the shoulders of giant large-language models.

The correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola yield a proof that Almost-ParityP = BP.ParityP, from which you can get a simpler proof of Toda's theorem. Details:

The STOC CFP says "The use of AI tools will not be weighed in the evaluation of the paper by the PC." Bill wonders why then do they ask for AI disclosure at all.

In my 1989 thesis I asked if there was an oracle separating IP from MIP. That was before we knew that MIP=NEXP, though that result doesn't relativize. Bouland, Huang, Natarajan, Shalit, Tal and Astra now answer the original question.

Because PSPACE-Completeness still matters www.wsj.com/tech/ai/...

This fall I'm joining the Leadership and Society Initiative at the University of Chicago, becoming a student where I started my academic career thirty-seven years ago. I hope to learn where I can best play a role to manage the weird times we are in. leadforsociety.uchic...

Breaking down the new STOC submission rules.

Want to be Bill's student? He doesn't care about your major, your minors, your honors or your grades.

A new risk for mathematicians: a colleague reports that immediately after they posted an abstract of their upcoming talk online, a student elsewhere used AI to derive proofs of the stated results and then posted it on the arxiv. My colleague hadn't posted to arxiv yet. Scummy. Watch out.

The Manufacturing Tech show is back in Chicago and AI takes center stage, or does it?

STOC call for papers is out. Deadline is November 2. acm-stoc.org/stoc202... New rules for the AI era: limited submissions, public posting and a required video. Is it a coincidence that the camera-ready deadline is April Fools Day?

Looks like every paper moving forward will have an AI declaration, even if it just says "We didn't use AI".

LAX is launching today, a way to connect natural mathematical language with Lean. They have a nice way to define complexity classes and can formalize some complexity results, for example nondeterministic space closed under complement

I'm a fan of publishing everything. It's not like we'll run out of space on the Internet. The good stuff will bubble up through social media and AI-powered searching.

I thought about k-server with Howard Karloff when we were both young U Chicago professors in the 90s. We even came up independently (as did many others) with the work algorithm, and now we know it actually works.

I was only being semi-serious two months ago.

Bill's take on all things AI and Math