@fortnow

Computational Complexity Theorist

 Chicago
lance.fortnow.com
Joined July 2008
  • Tweets6.4K
  • Following389
  • Followers6.9K
304Media
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.
10
11
1
89
7,649
Avi Wigderson surveys the recently departed Michael Rabin's research eccc.weizmann.ac.il/report/2…
12
33
5,157
Bill's thoughts on AI and Math blog.computationalcomplexity…
6
21
2,720
I asked Claude to summarize mathematicians reactions to October 6th github.com/fortnow/AI-Papers…
1
2
19
3,674
So why is it so hard to formalize computational complexity? it's not the hard stuff, but showing algorithms actually sit in polynomial time. blog.computationalcomplexity…
2
5
1
34
3,282
By request, a Claude rewrite of the Perfect-completeness 2-1 Games Theorem. github.com/fortnow/AI-Papers…

AI-Papers/perfect-completeness-2-to-1-expository.pdf at main · fortnow/AI-Papers

Expository rewrites of AI-generated theory papers (openai/math) - fortnow/AI-Papers

github.com
1
16
1,387
Moni Naor wins the 2026 Knuth Prize, the highest career award in theoretical computer science. sigact.org/Prizes/knuth/cita…
1
23
2
102
8,908
NYT Daily interviews Steven Strogatz on AI and Mathematics. nytimes.com/2026/10/13/podca… No spoilers but it takes an unexpected turn about 24 minutes in.

Mathematicians’ Latest Problem: What if A.I. Can Do Our Job?

In the span of just a few months, A.I. systems have solved some of the biggest outstanding problems in math — adding mathematicians to the list of those terrified of losing their job to the technol...

nytimes.com
5
18
1,571
Bill posts on his favorite of the OpenAI theorems. blog.computationalcomplexity…
1
14
63
11,931
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.
2
5
1
105
5,457
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. github.com/fortnow/AI-Papers…

AI-Papers/unique-games-theorem-expository.pdf at main · fortnow/AI-Papers

Expository rewrites of AI-generated theory papers (openai/math) - fortnow/AI-Papers

github.com
5
12
1
56
4,383
The existential threat from artificial intelligence is not that it will kill us all but that it will take away our relevance.
22
1
50
3,346
Lance Fortnow retweeted
Ollin Boer Bohan@madebyollinOct 6
Replying to @stevenstrogatz
🥹
1
15
5
78
17,982
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.computationalcomplexity… And a website to make it a little easier to browse OpenAI's TCS-related results lance.fortnow.com/openai-mat…
1
14
68
6,771
Lance Fortnow retweeted
OpenAI
@OpenAIOct 6
We’re releasing a broad range of new mathematical results produced by an internal frontier model. We’ve been consulting with the independent Advisory Group on Mathematics and Artificial Intelligence at the Institute for Advanced Study, and we have drawn on their advice and public recommendations to inform how we release these results. github.com/openai/math

GitHub - openai/math

Contribute to openai/math development by creating an account on GitHub.

github.com
1,897
6,311
4,766
40,760
22,661,105
For what it's worth, OpenAI's one-tape TM simulation (assuming correct) immediately implies RAM time t is in SPACE[t^{4/5}] github.com/openai/math/blob/… Not sure why they didn't mention this corollary! That was the whole point of my question.

math/preprints/Simulating-One-Tape-Time-in-Two-Fifths-Power-Space-September-25-2026/article.pdf at...

Contribute to openai/math development by creating an account on GitHub.

github.com
12
37
2
349
30,675
Lance Fortnow retweeted
Scott Kominers
@skominersOct 6
First off: 🤯. Utterly unreal result. Second: I'm seeing a lot of complaints about the fact that Anthropic contracted with human experts to write up the paper – but to a first-order, isn't this what the "Responsible Release" guidelines circulated last week say to do?
𝖬𝖺𝗁𝖽𝗂 𝖢𝗁. (bluesky:@mahdi.ch)@mahdi_tcs_Oct 6
The what now?! arxiv.org/abs/2610.06783v1

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in...

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial...

arxiv.org
25
30
7
390
61,936
Lance Fortnow retweeted
Daniel Litt
@littmathOct 5
Good article here (in which I am quoted). As always with questions in headlines, the answer to the question in this headline is "no." quantamagazine.org/is-ai-the…

Is AI the End of Math As We Know It? | Quanta Magazine

Mathematicians are facing the sudden shift with grief, anger, and a desperate search for fresh ideas: “If we don’t adapt, there’s just no more math in 50 years.”

quantamagazine.org
6
16
1
101
13,692
Bill looks at jobs that help create data to train AI. Sounds like all our jobs right now. blog.computationalcomplexity…
1
5
1,645
A few news items: Trump held back about a fifth of the NSF budget nytimes.com/2026/10/02/us/po… arXiv to limit submitters to two submissions per month blog.arxiv.org/2026/10/01/up…

Agency Diverted $1.4 Billion in Science Funds Mandated by Congress (Gift Article)

The move, affecting about one-fifth of the National Science Foundation’s primary research budget, is the latest sign of how the White House is asserting more control over grants.

nytimes.com
1
11
2,227
Load more