If I have seen farther, it is by standing on the shoulders of giant large-language models.
September 29, 2026 at 7:15 PM
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:
Details:
$\mathrm{Almost}\text{-}\oplus\mathrm{P} =...
Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between $\mathbb{F}_2$-polynomials and the XOR of majorities, we show that...
arxiv.org
September 29, 2026 at 2:21 PM
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:
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.
What is the points of AI-disclosure?
The STOC conference (and likely others) are requiring that a submission says how much AI was used. I can imagine the following options: 1) A...
blog.computationalcomplexity.org
September 28, 2026 at 1:04 PM
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.
$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize
We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson...
arxiv.org
September 26, 2026 at 4:54 PM
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.
September 24, 2026 at 7:14 PM
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...
leadforsociety.uchic...
September 23, 2026 at 10:09 PM
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...
leadforsociety.uchic...
Breaking down the new STOC submission rules.
The New STOC Rules for the AI Era
The 59th ACM Symposium on the Theory of Computing takes place in Atlanta next June, part of the Federated Computing Research Conference . I...
blog.computationalcomplexity.org
September 23, 2026 at 3:44 PM
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.
I don't care about majors, minors, or honors programs. Do you?
The following conversation is fictional. --------------------------- ALICE: (Looking over a student's record.) Hmm, let's see. She wants to ...
blog.computationalcomplexity.org
September 20, 2026 at 11:55 PM
Want to be Bill's student? He doesn't care about your major, your minors, your honors or your grades.
Reposted by Lance Fortnow
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.
Scummy.
Watch out.
September 18, 2026 at 9:36 AM
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.
Scummy.
Watch out.
The Manufacturing Tech show is back in Chicago and AI takes center stage, or does it?
AI and Manufacturing Redux
ITMS 2026 Two years ago I attended the International Manufacturing Technology Show in Chicago's McCormick Place and found a rather limited ...
blog.computationalcomplexity.org
September 17, 2026 at 10:15 PM
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?
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?
September 17, 2026 at 8:44 PM
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?
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".
September 17, 2026 at 5:12 PM
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
The Immerman–Szelepcsényi Theorem — lax-733996
Lax — an archive of formalized mathematical concepts and their proofs
laxarchive.org
September 17, 2026 at 2:31 PM
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.
September 16, 2026 at 4:39 PM
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.
A world without open problems
Here are some that fell today:
K-server: arxiv.org/abs/2609.15979
Matroid Secretary: arxiv.org/abs/2609.145...
Matrix Spencer: arxiv.org/abs/2609.15025
(Well Matrix Spencer was maybe also a few weeks ago, but who's counting? arxiv.org/abs/2608.28816 )
Here are some that fell today:
K-server: arxiv.org/abs/2609.15979
Matroid Secretary: arxiv.org/abs/2609.145...
Matrix Spencer: arxiv.org/abs/2609.15025
(Well Matrix Spencer was maybe also a few weeks ago, but who's counting? arxiv.org/abs/2608.28816 )
September 15, 2026 at 7:57 PM
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.
Does it seem like we're seeing an acceleration in new theorems, especially in combinatorics. Some proved by AI, some assisted by AI, some inspired by AI and some by humans trying to prove what they can before AI takes over.
September 14, 2026 at 10:16 PM
I was only being semi-serious two months ago.
Bill's take on all things AI and Math
Math, AI, and the Navier-Stokes Equations
On September 1, 2026: LANCE: I'm surprised you haven't blogged about OpenAI solving 10 open math problems. BILL: If I post every time an op...
blog.computationalcomplexity.org
September 14, 2026 at 2:08 PM
Bill's take on all things AI and Math
A tenet of the theory of computing is the interchangeability between program and data. So if an ML system uses a persistent writable memory, it could reprogram itself, potentially enabling recursive self-improvement, especially if many agents share the same storage space.
September 11, 2026 at 7:19 PM
A tenet of the theory of computing is the interchangeability between program and data. So if an ML system uses a persistent writable memory, it could reprogram itself, potentially enabling recursive self-improvement, especially if many agents share the same storage space.
Reposted by Lance Fortnow
Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
Complexity Theory At Carnegie Mellon
www.youtube.com
September 10, 2026 at 6:18 PM
Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
Reposted by Lance Fortnow
A group of 25 Fields Medalists, including myself, have made a joint declaration on Math and AI: mathandai.org . We welcome additional signatories. See also this article in the Economist announcing the declaration: www.economist.com/science-and-...
Declaration — Math and AI
Read the declaration and add your name.
mathandai.org
September 11, 2026 at 5:40 PM
A group of 25 Fields Medalists, including myself, have made a joint declaration on Math and AI: mathandai.org . We welcome additional signatories. See also this article in the Economist announcing the declaration: www.economist.com/science-and-...
Reposted by Lance Fortnow
AI is ravenous and is eating mathematicians' lunch. A long-standing problem is solved, others are in its sights. But is this more than just a problem about problems? Here's Fields Medallist James Maynard.
Read the Math and AI Declaration by 25 Fields Medallists: mathandai.org
Read the Math and AI Declaration by 25 Fields Medallists: mathandai.org
September 11, 2026 at 5:59 PM
AI is ravenous and is eating mathematicians' lunch. A long-standing problem is solved, others are in its sights. But is this more than just a problem about problems? Here's Fields Medallist James Maynard.
Read the Math and AI Declaration by 25 Fields Medallists: mathandai.org
Read the Math and AI Declaration by 25 Fields Medallists: mathandai.org
While P vs NP will remain out of the reach of AI, there are other complexity problems, like separating NP from L (log space) or BPP from NEXP, that might be more tractable and would still make an incredible splash.
September 11, 2026 at 12:19 PM
While P vs NP will remain out of the reach of AI, there are other complexity problems, like separating NP from L (log space) or BPP from NEXP, that might be more tractable and would still make an incredible splash.
Both OpenAI and Alpöge-Buckmaster heavily leaned on Lean in their Navier-Stokes announcements. Is this a new requirement for publishing?
Navier-Stokes and Lean
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 Ma...
blog.computationalcomplexity.org
September 9, 2026 at 4:53 PM
Both OpenAI and Alpöge-Buckmaster heavily leaned on Lean in their Navier-Stokes announcements. Is this a new requirement for publishing?
Another reminder that a solution to P v NP is not around the corner. Neither man or machine has even a viable approach.
September 9, 2026 at 12:56 AM
Another reminder that a solution to P v NP is not around the corner. Neither man or machine has even a viable approach.
The post I wrote in January 2025, "Our Days are Numbered", is coming true much faster than I expected.
"Our Days Are Numbered"
Slide in Lev Reyzin 's JMM talk "Problems in AI and ML for Mathematicians" Reyzin is paraphrasing Telgarsky. Posted with permission. Last we...
blog.computationalcomplexity.org
September 8, 2026 at 10:24 PM
The post I wrote in January 2025, "Our Days are Numbered", is coming true much faster than I expected.