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

I just wrote a sentence where without thinking I used the phrase "computer scientist" to mean an AI doing science.

Which of these people is not like the other? The story of Bill and the two Charles Lins blog.computationalco...

Princeton University Press is having a 70% off sale. You can pick up a paperback copy of The Golden Ticket for under $7.

Taking meditation lessons from René Descartes, why I don't believe that humans are just high-powered computers.

Congratulations to Thomas Rothvoss and Lang Liu, the inaugural winners of the Trevisan Prize at Bocconi University. cs.unibocconi.eu/trevisan-pri...

Bill asks "If you use AI in your work do you brag about it or hide it?" blog.computationalco... My thought: If you would have acknowledged a human doing the same thing, you should acknowledge the AI.

One of my kids told me that there are sides on the Internet, and that I'm on the wrong one.

In their new book "If Anyone Builds It, Everyone Dies," Yudkowsky and Soares argue that we can view an Artificially Super Intelligent agent as though it has its own agency and desires. But computers are a different beast.

Looks like blog.computationalco... is down. Hope to get it back up soon.

We went to a great new exhibit at the Chicago Field Museum about what happened after the asteroid hit that killed the dinosaurs. www.fieldmuseum.org/... Suppose you had the opportunity to go back in time to redirect that asteroid. Would you?

Clyde Kruskal remembers the 100th anniversary of the birth of his father Martin in a guest post.

Because of zero-knowledge SNARKs that rely on our sumcheck protocol, Algebraic Methods for Interactive Proof Systems (1992) with Lund, Karloff and Nisan is now my most cited paper edging out NEXP = MIP (1991) with Babai and Lund. Good to see the old paper getting some new love.

15 years ago I predicted self-driving cars five years ago. Better late than never.

Whenever someone tells me "wait until you see what quantum and AI will do together", I'm reminded of this passage from the book Harry Potter and the Deathly Hallows.

Bill talks about collecting research papers to be read later and how new technologies, like copy machines, have changed that process.

⏰ The 🧑‍🎓 travel support application and 👶 childcare support applications are both due in ~25h! The former is open to all students and postdocs (not necessarily authors of a paper). The latter provides financial support (to be used in any childcare-related way) to conference attendees! Links below↴

When I went to college in the early 80's, it was a faux pas to wear a backpack using both straps. Four decades later I still find myself slinging my backpack over one shoulder.

Sam Altman claimed that GPT-5 had "PhD-level" expertise. Before we can debate that point, what does it even mean?

Took my own advice and rewatched Sneakers. This line aged well. There's a war out there, old friend. A world war. And it's not about who's got the most bullets. It's about who controls the information. What we see and hear, how we work, what we think. It's all about the information!

Here's the answer to yesterday's question. Q: Suppose we have a Turing machine with a stay-put option, δ:QxΓ→QxΓx{L,R,S}. Can you create an equivalent Turing machine with only L,R moves without enlarging Q or Γ ? Answer in the picture. Formatted by AI.

Happy Pythagorean Triple Square Day! 3² + 4² = 5² (9/16/25) The next one is in one hundred years!

Want to remember Robert Redford - Sneakers, the 1992 movie where his character led a professional hacking team going after a device that will break any code. Better than it sounds.

I gave a homework bonus question that even AI couldn't solve. Can you? Suppose we have a Turing machine with a stay-put option, δ:QxΓ→QxΓx{L,R,S}. Can you create an equivalent Turing machine with only L,R moves without enlarging Q or Γ ?

Bill needs to learn how to disconnect when he is away.

Bill asks what counts as counting. Not the probabilistic method. blog.computationalco... [Ed note: Not information theory or Kolmogorov complexity either]

I thought tenure was the goal of my academic journey, but instead it was the catalyst for a life in constant transition.

We got a message saying we had a new campus staff license to ChatGPT. I'm thinking finally the university has realized that AI is a thing. But no--it was a phishing test from our tech support.