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.

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."

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...

A different way to fund science? 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.

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.

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

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...

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!

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

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.

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...

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.

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?

Let's hear it for the little theorems!

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!

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.

Every year I track the number of CS faculty jobs ads in the November issues of CRA News. It's not a perfect measure but it is forward looking to the upcoming job season. This year at 27 pages is down 69% from last year, 83% from the peak in 2022 and the lowest since 2011.

Will test-of-time awards pass the test of time? Bill has many questions.

About a decade ago, Ashok Goel introduced Jill Watson, an AI teaching assistant for an on-line course at Georgia Tech. Ten years later is his broader vision coming true. And is this a good thing?

If your institution wants to advertise Theory jobs to the FOCS 2025 attendees, a form has been set up on our website: focs.computer.org/2025/activit... The spreadsheet collating job openings in TCS will be made available to attendees (and online), to help graduating students and junior researchers.

Half my class used "transducer" in their homework solutions even though I never used the term in class. Sounds like it's from a bad sci fi movie: Bucky built a quantum transducer to travel to the fifth dimension.

A wonderful puzzle rescued from oblivion. www.theguardian.com/science/2025...

The death of the last grandchild of a former president drives Bill into action.

Hopefullly they also include test of space awards.

Computational Complexity Conference launches its first test of time award. Nominations due by March 2. computationalcomplex...

arXiv will no longer accept CS review articles unless they've already been peer reviewed because AI slop. doi.org/10.1038/d415... It's a shame arXiv has to do this. You can find good review papers in SIGACT News and the EATCS Bulletin.

As both the left and the right are arguing for some socialistic tendencies, I want to make the complexity argument for capitalism.

Palantir creates a fellowship for high school graduates as an alternative to college. Is this a warning to us in higher ed?

Bill talks about the so-called "Euclid". blog.computationalco... So Euclid brought understanding to his disciples and the world, though only through others writings. And did it 300 years before the other guy.

Venkatesan Guruswami selected as director of the Simons Institute for the Theory of Computing

‘The science world is ending’ #AcademicSky www.pbs.org/newshour/sho...

Nonuniformity in circuits always seemed to me to be more of a technicality, but artificial intelligence points to its surprising power.

Good discussion on the blog about a student who argued that exams should allow using AI since "future jobs won’t impose such artificial restrictions.” Students asking to know why they need to learn theory goes back to Euclid. blog.computationalco... 1/2

Bill doesn't care.

STOC 2026 is offering experimental pre-submission feedback using an AI tool optimized for checking mathematical rigor. Results won't go to PC or be used for training purposes. Opt-in via the submission server by November 1. Details: acm-stoc.org/stoc202... CFP: acm-stoc.org/stoc202...

I'm teaching Intro to Theoretical Computer Science for the first time in nearly a decade. The theorems have (mostly) stayed the same, but everything else seems different.

ChatGPT pulse yesterday on its own accord saw that I was teaching basic circuit in my class, and it gave me formatted notes on a high-level intuitive approach to the switching lemma. Even had the class date, time and location. Bowing to my AI overloads, I used the example in my lecture today.

Some good news on the visa front. Foreign students at US universities won't be subject to the $100K H1-B Fee.

Bill wishes everyone a belated Pythagorean day. blog.computationalco... I'm old enough to remember 12:34 on 5/6/78. Everything else has higher Kolmogorov complexity.

Nominations are open for the IEEE/Computer Society TCMF Distinguished Service Award to be presented at the upcoming FOCS conference. Nomination deadline November 15.

Every fall I post about the upcoming faculty job market in theoretical computer science, diving into academia more generally. Get ready for a bumpy ride.

You certainly shouldn't count on me for investment advice but I want to say something about trying to time bubbles. Here is a piece from a New York Times article on the tech bubble of the 90's. 1/2