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 quadratic improvement in the amount of memory you need to simulate time.

Simulating Time with Square-Root Space by Ryan Williams

Any time \(t(n)\) algorithm can be simulated in space \(O(\sqrt{t(n)\log t(n)})\) greatly improving the \(O(t(n)/\log t(n))\) result from the 70's. Ryan's work makes strong use of last year's space efficient tree evaluation by James Cook and Ian Mertz. More in my February post and a Quanta article which did a better job explaining the importance of the result than I could.

Bill is also excited by the new \(O(m\log^{2/3}n)\) single-sourced shortest path algorithm by Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu and Longhui Yinthat that beats out Dijkstra on sparse graphs. 

Last year I wrote

We're heading to a perfect storm for US higher education with the oncoming trains of the new administration, artificial intelligence, fiscal challenges and the demographic cliff. Hang on tight, it's going to be a bumpy ride.

Bumpy is an understatement and we're just starting the ride. Limited immigration, National Science Foundation woes in its 75th anniversary, and a drop in computer science enrollments as AI continues to suck up the atmosphere. Do we buckle down or should we completely rethink our institutions? 

In the spirit of all the AI wrapped content, I asked Claude to put together a full year in review for this blog. This is getting scarily good.

We remember George Foreman, Frank Gehry, Ray Laflamme, Tom Lehrer, Charles Lin, Pradyut Shah and Tom Stoppard. 

We thank our guest posters Eric Allender, Daniel Fernández and Alberto Fraile, Clyde Kruskal and Nick Sovich.

See you all in January!

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 related to the arts and creatives in some way. Art studios of all kinds, from fine art to photography, music instrument sales, repairs and instruction, an opera company and various music ensembles, puppetry, jewelry makers, authors, interior decorators, a store that sells music scores on paper and an independent books store, and much more. 

On the evenings of the second Friday of the month, the building has an open house, so you can visit the art studios and hear some music performances in small studios. You can stop by the Exile in Bookville bookstore and have Keir Graff sign a copy of his recent coffee table book about the building. 

The building started as the Studebaker building in 1885 as a factory and showroom for horse-drawn carriages. By 1896, the Studebaker family converted the building to studios for artists, architects, musicians and others and has more or less remained that way ever since. The big theater in the building, recently renovated, still bears the family name.

As a one-time tuba player, I appreciate that Arnold Jacobs, principal tubist of the Chicago Symphony for 44 years and perhaps the greatest to play the instrument, taught tuba from an office in the building.

Marker for Arnold Jacobs' Studio

The building is so low tech, it has the last remaining manually operated elevators in the city. It's not that everyone is anti-technology. Most studios have a computer to keep up with finances, emails, web pages and social media. But that's tech in the background. In a world focused on technology, nice to see a building in Chicago devoted to those who still create in a magical place that stands the test of time.

Weird Al vs Weird AI

 ONE

The following headline confused me:
 

                  Trump, 79, Deletes Weird AI Video Shilling Magic Beds (see here). 

Was Weird Al selling magic beds? Magic beds?! How does that relate to President Trump? What’s going on?

The problem is the font: a capital I (as in AI) can look like a lowercase l (as in Al).
So the headline should really be:

Trump, 79, Deletes Weird Artificial Intelligence Video Shilling Magic Beds.

This case is particularly confusing because:

a) Weird AI videos clearly means Videos that Weird Al has that go with his songs. 

While we’re on this topic, here are some Weird Al videos related to computer science or math:

Don't Download This Song 

 It's all about the Pentiums

 Polka Patterns 

The first two  songs are dated but I still like them. They also show that Weird Al has had (and still has) a long career. 

b) The story, even when understood completely, is really weird. 

TWO

I pointed out the Weird AI vs Weird Al issue to a fellow Weird Al fan, and he emailed me the following links:

McDonald's Making job Applicants Take Weird AI Personality Tests

MAGA Rep Weights in on Sydney Seeney Jeans Debate with Weird AI Ad

A Weird AI Camera With a Human Name is Coming for Your Cell Phone

Leith Ross Denounces Weird AI Songs Uploaded to Their Spotify Profile

Why We Don't Believe MIT Nanda's Weird Al Study

Anthropic Researchers Discover the weird AI Proble: Why thinking longer makes models dumber

Samsung phones are getting a weird AI shopping platform nobody asked for

THREE

0) The one with Weird AI Songs is the most confusing since that clearly means songs by Weird Al. 

1) Am I the first person to notice this? Of course not-- see here

2) Has someone used this confusion? Of course--see here

3) Will this confusion help or hurt Weird AL's career? Time will teLL.

Learning the Mathematical Process

Watching Mathematicians at Work (AI generated)

The Smithsonian Natural History Museum has a FossiLab where visitors can peek through windows watching scientists prepare fossils for conservation. Maybe we should have a similar exhibit at math museums or universities. How else can we learn what mathematicians do? 

In 2025, artificial intelligence has achieved gold medal status at the International Mathematical Olympiad but so far has only contributed modestly in finding new theorems. Of course, finding and proving new theorems requires a different set of skills than competition problems but it goes further than that.

The Internet has considerable text and video on how to solve math competition problems that machine learning systems can train on. On the other hand, mathematical research papers usually have little more than theorems and proofs. Maybe some intuition. Rarely do papers go into the thinking process and the false steps that one takes until one finds the proof. For some problems I've spent weeks proving a theorem but only the last day's work gets written up.

Now I doubt many mathematicians would give up their privacy and time to train AI systems to take over their jobs, but just suppose we wanted to do so. We could equip every mathematician with a camera recording every mathematical conversation and everything they write, especially the ideas that don't pan out. We can transcribe it all and feed it into an ML system. But it probably won't be enough.

Trouble is most mathematical breakthroughs just happen inside of people's heads. If you ask a mathematician how they came up with the clever idea that led to a major new result, they can rarely truly explain the process behind it. Not unlike neural nets. 

If machines can't learn to prove theorems by watching mathematicians, perhaps the route mathematicians take: A grad school slog towards PhD research and learning from endless failure. 

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 his works whose themes I think will be of interest to my readers (Or at least to me—your mileage may vary.)

1) Rosencrantz and Guildenstern are Dead (1966)

This is Hamlet told from the point of view of two minor characters who, in Shakespeare’s original, can best be described as plot furniture.

The play begins with, R and G are flipping coins. R bets heads ninety-two times in a row and wins each one. The play explores determinism and free will, as well as the mathematical question: At what point should you stop flipping coins and go buy a lottery ticket?

There is also a movie for this one. I think this is better as a play. 

2) Jumpers (1972)

A play about academic philosophers—so naturally it includes gymnastics, both literal and intellectual. There’s also a murder mystery, discussions of God, and enough moral philosophy to power an entire semester of office-hour arguments.

3) Travesties (1974) 

This play Imagines that Vladmir Lenin, James Joyce, and Tristan Tzara (a Dadaist poet, see here for the Dada Art Movement) met in Zurich in 1917. They actually were in Zurich in 1917, but the events are narrated by an unreliable octogenarian, so accuracy is...doubtful.

Literature, politics, and art are explored, often simultaneously.

4) Arcadia (1993)

The Stoppard play with the most math—a sentence that delights mathematicians and terrifies theater majors.

It takes place in two time periods: 1809 and 1993.

In 1809, a 13-year-old girl named Thomasina Coverly is (i) trying to prove Fermat’s Last Theorem and (ii) inventing chaos theory by stirring pudding. (This is the only known instance of dessert contributing to mathematics other than pie and muffins.)

In 1993, a historian is working on a theory about Lord Byron, which is only slightly less complicated than Fermat's Last Theorem.

Themes: math, determinism, academia, and the strong correlation between intellectual brilliance and household messes.

Note that this was written a year before FLT was proved. If it had come out a year after FLT was proved this would not change anything since (i) Thomasina Coverly is working in 1809, and (ii) FLT was still a well-known problem when the play came out. If the play had come out in 2025, then this might be a problem since FLT is not nearly as well-known as it was in 1993. 

Some say that FLT being proved was bad for math since it was 

(a) understandable to the non mathematician, 

(b) had prize money attached to it, 

(c) had the wonderful margin story, and 

(d) was open for many years.

(e) there are many poems about it, see here, which is a consequence of a,b,c,d. They were written without ChatGPT.   This criteria is no longer important since ChatGPT allows you to write poems about any math problem you want. I blogged on that here.

 I don't think anything has come close to replacing FLT.

 P vs NP: (a)-it's hard to get across to non-math people what a problem is , (b)-I think it's well known but perhaps I wouldn't know since the non-math people I hang out with know about it from me, (c)-no, (d)-no (hmm- is 50+years a long time?) (e)

Goldbach's conjecture has (a) and (d). As for (b): at one time there was a million dollar prize for solving it, see here, as a way to promote the book Uncle Petros and Goldbach's Conjecture but I think the prize expired. The link to find out the contest rules just points to that book companies website. In any case, this prize was not that well known.

While I would not expect a problem to have (c), does any open problem have (a), (b), some story like (c), and (d)? I doubt it.

5) Enigma (2001)

A fictional film about cracking the Enigma code.

Despite expectations, Alan Turing does not appear, nor is he even mentioned. This confused me, since Andrew Hodges's 1983 biography is titled Alan Turing: The Enigma (See here) which was the inspiration for the movie The Imitation Game.

Note that Enigma-the-movie has zero real people, but Travesties-the-play has three real people.

TWO) The Tom Stoppard Prize

The Tom Stoppard Prize was established in 1983 and first awarded in 1984. It is given annually for:
 

outstanding primarily non-fiction work by a writer of Czech origin.

This raises a question: Which is the greater honor—winning an award, or having one named after you while you’re still alive? The answer probably depends on both the award you receive and the award named after you.

In computer science, the only award I know named after a living person is the Knuth Prize. If there are others, leave a comment.

If you ever get this trivia question: 

What do Tom Stoppard and Donald Knuth have in common?

you now know the answer: They were both famous enough to be turned into prizes while they could still appreciate it.

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. have sped up the pace of math research. Wide variety of opinions but the broad consensus seems to be “yes,” among those I’ve spoken to.

— Daniel Litt (@littmath) October 30, 2025

and Bill's recent post on finding papers on the web I would tell the story of the before times.

In the 1980s if you wanted to read a paper, you either had to find it in a journal or conference proceedings or have it mailed to you. You could reach out to an author or SIGACT News would publish a list of tech reports from various universities. Departments would keep a master copy of each paper. You would send a stamped self-addressed envelope to the department which would copy the paper, put on a tech-report cover and send it back to you.

If you had a particularly exciting result, you would share it by physically mailing it out to your colleagues. I found out about the latest circuit results from Håstad and Razborov, as they sent papers to my advisor Michael Sipser, often hand-written and in Razborov's case in Russian. Neil Immerman sent a copy of his nondeterministic space closed under complement paper to Sipser but he was away for the summer. I found out about the result from a Berkeley talk announcement. 

Email wasn't a common method of communication until the mid-80's and it wasn't until a few years after that that people figured out how to send papers by putting the latex or postscript text directly in the email. This was before attachments and PDFs. Old mail systems put a ">" before From so it wouldn't be confused as a header and LaTeX rendered ">From" as "¿From" which you'd often see in conference papers from around that time.

In my first year as an assistant professor in 1989-90, there was a flurry of emailed papers marking (and causing) the quick progress we had in interactive proofs, described so well by László Babai's E-mail and the Unexpected Power of Interaction. Babai had a warning about researchers disadvantaged because they weren't receiving these emails.

I got tired of emailing papers so as soon as the web became a thing in 1993, I put all my papers online and have maintained it since. Now with sites like arXiv and ECCC, everyone has access to the latest and greatest in complexity.

Now how long before the next generation asks how we discovered papers before we had chatbots to find them for us?