Reposted by Lance Fortnow
A really important piece. The times when we have opened our country to talented people from around the world are among the moments when America has been truly great. Trump is destroying that legacy and fomenting unconscionable racism.
www.nytimes.com/2025/12/29/o...
www.nytimes.com/2025/12/29/o...
Opinion | One of America’s Most Successful Experiments Is Coming to a Shuddering Halt
www.nytimes.com
December 29, 2025 at 12:37 PM
A really important piece. The times when we have opened our country to talented people from around the world are among the moments when America has been truly great. Trump is destroying that legacy and fomenting unconscionable racism.
www.nytimes.com/2025/12/29/o...
www.nytimes.com/2025/12/29/o...
ACM digital library is now open access.
https://dl.acm.org/
They have moved to an author/institution pay model, and features like stats and advanced search now require a "premium" subscription. I do my searching in Gemini now, and Google Scholar has good stats.
https://dl.acm.org/
They have moved to an author/institution pay model, and features like stats and advanced search now require a "premium" subscription. I do my searching in Gemini now, and Google Scholar has good stats.
December 26, 2025 at 8:35 PM
ACM digital library is now open access.
https://dl.acm.org/
They have moved to an author/institution pay model, and features like stats and advanced search now require a "premium" subscription. I do my searching in Gemini now, and Google Scholar has good stats.
https://dl.acm.org/
They have moved to an author/institution pay model, and features like stats and advanced search now require a "premium" subscription. I do my searching in Gemini now, and Google Scholar has good stats.
TIL that now, in Australia's summer, Brisbane is a half hour behind Adelaide in time despite being nearly 900 miles further east.
December 23, 2025 at 12:12 AM
TIL that now, in Australia's summer, Brisbane is a half hour behind Adelaide in time despite being nearly 900 miles further east.
Sometimes I feed my favorite open complexity problems into LLMs to see what they say. Too often they say something like "I can't solve that because Fortnow's blog says its an open question."
December 22, 2025 at 9:28 PM
Sometimes I feed my favorite open complexity problems into LLMs to see what they say. Too often they say something like "I can't solve that because Fortnow's blog says its an open question."
Time for the Computational Complexity Year-in-Review and this year's theorem of the year
blog.computationalco...
New this year, The Complexity Blog Wrapped by Claude
lance.fortnow.com/bl...
blog.computationalco...
New this year, The Complexity Blog Wrapped by Claude
lance.fortnow.com/bl...
Complexity Year in Review
An easy choice for paper of the year, a paper that has nothing to do with randomness, interaction, quantum, circuits or codes. Just a near q...
blog.computationalcomplexity.org
December 22, 2025 at 6:27 PM
Time for the Computational Complexity Year-in-Review and this year's theorem of the year
blog.computationalco...
New this year, The Complexity Blog Wrapped by Claude
lance.fortnow.com/bl...
blog.computationalco...
New this year, The Complexity Blog Wrapped by Claude
lance.fortnow.com/bl...
A different way to fund science?
www.wsj.com/opinion/...
www.wsj.com/opinion/...
December 19, 2025 at 2:36 PM
A different way to fund science?
www.wsj.com/opinion/...
www.wsj.com/opinion/...
In the holiday spirit, my trip to a magical place where people create things without new fangled technology. And I didn't even have to leave Chicago.
A Place Away From Tech
The Fine Arts Building Last week, I partook of the second Fridays open house in the The Fine Arts Building , ten floors of offices all re...
blog.computationalcomplexity.org
December 17, 2025 at 10:44 PM
In the holiday spirit, my trip to a magical place where people create things without new fangled technology. And I didn't even have to leave Chicago.
Google reports out on their experiment giving optional feedback generated on Gemini to pre-submission STOC 2026 papers. Upshot: Pretty useful.
research.google/blog...
Honestly, everyone should run their paper through a reasoning LLM before submitting to an archive, conference or journal.
research.google/blog...
Honestly, everyone should run their paper through a reasoning LLM before submitting to an archive, conference or journal.
December 16, 2025 at 4:39 PM
Google reports out on their experiment giving optional feedback generated on Gemini to pre-submission STOC 2026 papers. Upshot: Pretty useful.
research.google/blog...
Honestly, everyone should run their paper through a reasoning LLM before submitting to an archive, conference or journal.
research.google/blog...
Honestly, everyone should run their paper through a reasoning LLM before submitting to an archive, conference or journal.
I'll be in Oxford in England from January 8 to March 26 as a visiting fellow at Magdalen College. Feel free to reach out if you want to connect.
December 15, 2025 at 2:32 PM
I'll be in Oxford in England from January 8 to March 26 as a visiting fellow at Magdalen College. Feel free to reach out if you want to connect.
Weird AI is yanking Bill's chain
Weird Al vs Weird AI
ONE The following headline confused me: Trump, 79, Deletes Weird AI Video Shilling Magic Beds (see here ). Was Weird...
blog.computationalcomplexity.org
December 14, 2025 at 3:34 PM
Weird AI is yanking Bill's chain
Mathematicians work in mysterious ways. Perhaps that's why AI find proving theorems so challenging.
Learning the Mathematical Process
Watching Mathematicians at Work (AI generated) The Smithsonian Natural History Museum has a FossiLab where visitors can peek through window...
blog.computationalcomplexity.org
December 11, 2025 at 4:01 PM
Mathematicians work in mysterious ways. Perhaps that's why AI find proving theorems so challenging.
Bill Gasarch is running REU-CAAR
(Research Experience for undergraduates- Combinatorics, algorithms, and AI for Real Problems) at the University of Maryland next summer. A great opportunity for undergrads. Comes with $7K+room and board.
www.cs.umd.edu/proje...
(Research Experience for undergraduates- Combinatorics, algorithms, and AI for Real Problems) at the University of Maryland next summer. A great opportunity for undergrads. Comes with $7K+room and board.
www.cs.umd.edu/proje...
December 9, 2025 at 11:40 PM
Bill Gasarch is running REU-CAAR
(Research Experience for undergraduates- Combinatorics, algorithms, and AI for Real Problems) at the University of Maryland next summer. A great opportunity for undergrads. Comes with $7K+room and board.
www.cs.umd.edu/proje...
(Research Experience for undergraduates- Combinatorics, algorithms, and AI for Real Problems) at the University of Maryland next summer. A great opportunity for undergrads. Comes with $7K+room and board.
www.cs.umd.edu/proje...
Reposted by Lance Fortnow
The pre-recorded videos (for the talks whose authors opted in to submit one) are now available on our YouTube channel: m.youtube.com/@FOCS2025
They're also linked from the main website's schedule!
They're also linked from the main website's schedule!
FOCS 2025
Videos from the 66th IEEE Symposium on Foundations of Computer Science (FOCS) 2025
m.youtube.com
December 9, 2025 at 4:40 AM
The pre-recorded videos (for the talks whose authors opted in to submit one) are now available on our YouTube channel: m.youtube.com/@FOCS2025
They're also linked from the main website's schedule!
They're also linked from the main website's schedule!
The architect Frank Gehry passed away last Friday at 96. Among many other projects, he designed the Stata Center, the CS building at MIT.
December 8, 2025 at 11:46 PM
The architect Frank Gehry passed away last Friday at 96. Among many other projects, he designed the Stata Center, the CS building at MIT.
Bill remembers Tom Stoppard
Tom Stoppard 1937-2025
The playwright Tom Stoppard passed away at the age of 88 on Nov. 29, 2025. ONE) He wrote many plays and some movies. Below I highlight ...
blog.computationalcomplexity.org
December 8, 2025 at 12:25 AM
Bill remembers Tom Stoppard
University of Wisconsin is establishing a College of Computing and Artificial Intelligence, one of the first major research university with a college with AI in its name.
College of Computing and Artificial Intelligence – UW–Madison
A new era for computing and AI at UW–Madison Technology is transforming every aspect of society—including health care and agriculture, education and science, business and entrepreneurship, and the arts and humanities. At the core of this technological shift are computing and artificial intelligence, which are rapidly shaping how we live, work, innovate, and learn. To …
cai.wisc.edu
December 5, 2025 at 3:20 PM
University of Wisconsin is establishing a College of Computing and Artificial Intelligence, one of the first major research university with a college with AI in its name.
My thoughts on the late 80'-early 90's transition for research paper distribution from mail to email to the web.
Finding Papers Before the Web
Inspired by Daniel Litt's X Post Started asking mathematicians whose career started before the internet if they think Google, email, etc. ha...
blog.computationalcomplexity.org
December 5, 2025 at 12:45 AM
My thoughts on the late 80'-early 90's transition for research paper distribution from mail to email to the web.
My little theorem paper is now on arXiv: arxiv.org/abs/2512.0...
How I had AI write the paper is more interesting than the paper itself. It felt like working with a grad student. docs.google.com/docu...
How I had AI write the paper is more interesting than the paper itself. It felt like working with a grad student. docs.google.com/docu...
Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
We compare the complexity of the search and decision problems for the complexity class S2P. While Cai (2007) showed that the decision problem is contained in ZPP^NP, we show that the search...
arxiv.org
December 3, 2025 at 4:37 PM
My little theorem paper is now on arXiv: arxiv.org/abs/2512.0...
How I had AI write the paper is more interesting than the paper itself. It felt like working with a grad student. docs.google.com/docu...
How I had AI write the paper is more interesting than the paper itself. It felt like working with a grad student. docs.google.com/docu...
It seems the programming world is divided among the people who say AI is useless to them, and others who just use it effectively. Bill hosts a debate.
Does ChatGPT really help programmers?
BILL: I honestly do not know whether ChatGPT will make programmers more productive. (I am not touching question of whether it puts progra...
blog.computationalcomplexity.org
December 1, 2025 at 2:44 PM
It seems the programming world is divided among the people who say AI is useless to them, and others who just use it effectively. Bill hosts a debate.
Happy AI day!
November 30, 2020: AlphaFold announced.
November 30, 2022: ChatGPT released.
We're only three years into the generative AI era.
November 30, 2020: AlphaFold announced.
November 30, 2022: ChatGPT released.
We're only three years into the generative AI era.
November 30, 2025 at 1:08 PM
Happy AI day!
November 30, 2020: AlphaFold announced.
November 30, 2022: ChatGPT released.
We're only three years into the generative AI era.
November 30, 2020: AlphaFold announced.
November 30, 2022: ChatGPT released.
We're only three years into the generative AI era.
Following my blog post yesterday, I "vibe coded" a short research paper on my little theorem on S2P search, maybe more of an observation.
lance.fortnow.com/pa...
Blog post: blog.computationalco...
Now what should I do with it?
lance.fortnow.com/pa...
Blog post: blog.computationalco...
Now what should I do with it?
November 25, 2025 at 4:38 PM
Following my blog post yesterday, I "vibe coded" a short research paper on my little theorem on S2P search, maybe more of an observation.
lance.fortnow.com/pa...
Blog post: blog.computationalco...
Now what should I do with it?
lance.fortnow.com/pa...
Blog post: blog.computationalco...
Now what should I do with it?
Let's hear it for the little theorems!
The Little Theorems
Last week we had a talk by Purdue philosophy professor Eamon Duede Tail Novelty, Knowledge Collapse, and Useful Frictions in Science . In p...
blog.computationalcomplexity.org
November 24, 2025 at 2:25 PM
Let's hear it for the little theorems!
Well, it works in theory...
Cryptology Group Held an Election, but Can’t Decrypt the Results
A global group of researchers was unable to read the vote tally, after an official lost one of three secret code keys needed to unlock a hyper-secure election system.
www.nytimes.com
November 22, 2025 at 10:31 PM
Well, it works in theory...
I vibe coded using Google Antigravity to fix the links in my blog that went to the old blog URLs. You can now navigate though the Foundations of Complexity posts again.
blog.computationalco...
It's an AI miracle!
blog.computationalco...
It's an AI miracle!
Foundations of Complexity<br> Lesson 1: What is a computer?
Next Lesson
This is the first of a long series of posts giving an informal
introduction to computational complexity.
Computational comp...
blog.computationalcomplexity.org
November 20, 2025 at 11:27 PM
I vibe coded using Google Antigravity to fix the links in my blog that went to the old blog URLs. You can now navigate though the Foundations of Complexity posts again.
blog.computationalco...
It's an AI miracle!
blog.computationalco...
It's an AI miracle!
Carmichael numbers, composites that "look like" primes, force us to use fancier primality tests like Miller-Rabin. Less known is that Miller-Rabin actually factors those Carmichaels.
Factoring Carmichael Numbers
Carmichael Numbers are the bane of probabilistic primality algorithms. You have to go through extra steps just to handle these relatively ra...
blog.computationalcomplexity.org
November 20, 2025 at 8:10 PM
Carmichael numbers, composites that "look like" primes, force us to use fancier primality tests like Miller-Rabin. Less known is that Miller-Rabin actually factors those Carmichaels.