January 28, 2026 at 6:20 PM
I'm perfectly happy having AI models trained on all my research papers and everything else I've publicly written, and I hope others feel the same. Best to have the models know as much about computational complexity as possible if we want to best further the field.
January 26, 2026 at 7:17 PM
I'm perfectly happy having AI models trained on all my research papers and everything else I've publicly written, and I hope others feel the same. Best to have the models know as much about computational complexity as possible if we want to best further the field.
England weather has been as advertised, cold, dark and damp. I haven't seen dry ground since I got here two weeks ago.
Still we're 50 degrees warmer than Chicago today.
Still we're 50 degrees warmer than Chicago today.
January 23, 2026 at 5:25 PM
England weather has been as advertised, cold, dark and damp. I haven't seen dry ground since I got here two weeks ago.
Still we're 50 degrees warmer than Chicago today.
Still we're 50 degrees warmer than Chicago today.
The 2026 Michael and Sheila Held Prize goes to Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer and Muli Safra for their work on the 2-to-2 Games Theorem.
Michael and Sheila Held Prize – NAS
The Michael and Sheila Held Prize is presented annually to honor outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent…
www.nasonline.org
January 23, 2026 at 3:00 PM
The 2026 Michael and Sheila Held Prize goes to Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer and Muli Safra for their work on the 2-to-2 Games Theorem.
Reposted by Lance Fortnow
Congrats to Irit Dveer Dinur of the Institute for Advanced Study & Weizmann Insitute, #NASmember Subhash Khot of New York University, Guy Kindler of @hebrewuniversity.bsky.social, Dor Minzer of @mit.edu, and Muli Safra of Tel Aviv University, winners of the 2026 Michael and Sheila Held Prize! (1/2)
January 22, 2026 at 3:56 PM
Congrats to Irit Dveer Dinur of the Institute for Advanced Study & Weizmann Insitute, #NASmember Subhash Khot of New York University, Guy Kindler of @hebrewuniversity.bsky.social, Dor Minzer of @mit.edu, and Muli Safra of Tel Aviv University, winners of the 2026 Michael and Sheila Held Prize! (1/2)
In academia we have two main communities, our department and our academic field. At Oxford, community seems to lie mainly in the colleges.
Community
I once had a provost who felt that academic departments hindered the university as they tended to silo the faculty. He would argue we should...
blog.computationalcomplexity.org
January 22, 2026 at 4:52 PM
In academia we have two main communities, our department and our academic field. At Oxford, community seems to lie mainly in the colleges.
New ACM Fellows include Swarat Chaudhuri, Javier Esparza, Paolo Ferragina, Ken-Ichi Kawarabayashi, Aggelos Kiayias, Alistair Moffat, Noam Nisan, Ariel Procaccia, Oded Regev, Natarajan Shankar, Stephanie Weirich, Adam Wierman and Ke Yi.
awards.acm.org/fello...
awards.acm.org/fello...
January 21, 2026 at 4:32 PM
New ACM Fellows include Swarat Chaudhuri, Javier Esparza, Paolo Ferragina, Ken-Ichi Kawarabayashi, Aggelos Kiayias, Alistair Moffat, Noam Nisan, Ariel Procaccia, Oded Regev, Natarajan Shankar, Stephanie Weirich, Adam Wierman and Ke Yi.
awards.acm.org/fello...
awards.acm.org/fello...
Bill asks how can we handle students using AI for homework and I give my thoughts.
Short Answer: Not much.
Short Answer: Not much.
What to do about students using ChatGPT to do their homework?
Students are using ChatGPT to do their HW. Here are things I've heard and some of my thoughts on the issue (Lance also added some comments)....
blog.computationalcomplexity.org
January 20, 2026 at 6:45 AM
Bill asks how can we handle students using AI for homework and I give my thoughts.
Short Answer: Not much.
Short Answer: Not much.
Reposted by Lance Fortnow
This is scientists’s version of tearing down parts of the White House.
The National Science Foundation sign on our Eisenhower Av building is now gone.
The NSF mural in the foyer is removed and torn off in sheets.
We were supposed to celebrate the 75th anniversary of the agency in May 2025. That never happened.
The NSF mural in the foyer is removed and torn off in sheets.
We were supposed to celebrate the 75th anniversary of the agency in May 2025. That never happened.
January 18, 2026 at 3:16 AM
This is scientists’s version of tearing down parts of the White House.
A three-decade-old open problem of mine just got solved! Matt Kovacs-Deak, Daochen Wang and Rain Zimin Yang showed that if a Boolean function f is exactly computed by a low-degree rational function, the quotient of two polynomials, then f has low decision-tree complexity.
1/2
1/2
January 14, 2026 at 3:06 PM
A three-decade-old open problem of mine just got solved! Matt Kovacs-Deak, Daochen Wang and Rain Zimin Yang showed that if a Boolean function f is exactly computed by a low-degree rational function, the quotient of two polynomials, then f has low decision-tree complexity.
1/2
1/2
RIP Scott Adams www.nytimes.com/2026...
Whatever you think of the man, his Dilbert creations captured the tech world. Just call me Dan.
1/2
Whatever you think of the man, his Dilbert creations captured the tech world. Just call me Dan.
1/2
January 13, 2026 at 4:46 PM
RIP Scott Adams www.nytimes.com/2026...
Whatever you think of the man, his Dilbert creations captured the tech world. Just call me Dan.
1/2
Whatever you think of the man, his Dilbert creations captured the tech world. Just call me Dan.
1/2
In the LLM era, I'm finding people are not very tolerent of typos and grammatical issues.
January 12, 2026 at 11:18 PM
In the LLM era, I'm finding people are not very tolerent of typos and grammatical issues.
Bill's post smells like an egg frying on the sidewalk on a winter's day.
Is `smells like' commutative?
1) Smells Like... Something In many TV shows having to do with murder (and there are plenty of them), I’ve heard the following exchange: ...
blog.computationalcomplexity.org
January 12, 2026 at 3:55 PM
Bill's post smells like an egg frying on the sidewalk on a winter's day.
You rarely see mathematicians claiming that AI systems will solve any of the Clay Math Millennium problems in the near future. It's not that AI is improving its math capabilities quickly. More so that the Millennium math problems are far more difficult that any of us can imagine.
January 9, 2026 at 6:28 PM
You rarely see mathematicians claiming that AI systems will solve any of the Clay Math Millennium problems in the near future. It's not that AI is improving its math capabilities quickly. More so that the Millennium math problems are far more difficult that any of us can imagine.
I made it to Oxford for my visiting fellowship at Magdalen College. Time to return to Computational Depth, measuring information with randomness removed.
Computational Depth
I'm posting from Oxford University where I will be spending the "Hilary Term" (through late March) as a visiting fellow at Magdalen College....
blog.computationalcomplexity.org
January 9, 2026 at 1:59 PM
I made it to Oxford for my visiting fellowship at Magdalen College. Time to return to Computational Depth, measuring information with randomness removed.
Good budget news for the National Science Foundation. Well, good compared to what might have been.
FY26 Appropriations Update: Congressional Appropriators Release Minibus Spending Bill, Rejecting Harsh Funding Cuts for NSF, DOE SC, NIST, & NASA - GovAffairs
Analysis of the Fiscal Year 2026 minibus legislation containing the CJS and E&W funding legislation. Analysis of the Fiscal Year 2026 minibus legislation containing the CJS and E&W funding legislation.
cra.org
January 7, 2026 at 11:19 PM
Good budget news for the National Science Foundation. Well, good compared to what might have been.
From Slop to Verification to Collaboration to Generation, AI is changing how we write research papers and its getting better quickly.
AI and Research Papers
2026 will be a year of AI disruption across all of academia. Let's start by talking about AI is changing how we write research papers. Not t...
blog.computationalcomplexity.org
January 5, 2026 at 10:03 PM
From Slop to Verification to Collaboration to Generation, AI is changing how we write research papers and its getting better quickly.
And God Created Woman, then took her away at the end of 2025, making Brigitte Bardot a recipient for Bill's Betty White Award.
The Betty White Award for 2025
The Betty White Award goes to people who die at the end of the year--- too late to be on those articles with titles like ...
blog.computationalcomplexity.org
January 3, 2026 at 6:39 PM
And God Created Woman, then took her away at the end of 2025, making Brigitte Bardot a recipient for Bill's Betty White Award.
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.