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.
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.
This year at 27 pages is down 69% from last year, 83% from the peak in 2022 and the lowest since 2011.
November 19, 2025 at 8:48 PM
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.
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.
Test of Time Awards: A Good Idea but ....
Since there is now a CCC Test-of-Time Award, see here , (CCC stands for Computational Complexity Conference), I decided to look at other T...
blog.computationalcomplexity.org
November 16, 2025 at 2:30 PM
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?
The Future of Teaching Assistants
In 2016, in the pre-transformer times, Georgia Tech professor Ashok Goel gave a prescient TEDx Talk on an AI teaching assistant for his la...
blog.computationalcomplexity.org
November 12, 2025 at 10:41 PM
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?
Reposted by Lance Fortnow
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.
The spreadsheet collating job openings in TCS will be made available to attendees (and online), to help graduating students and junior researchers.
FOCS 2025: Job openings for postdocs and researchers
Please provide details about any theory job openings in your group (e.g., postdoc openings, research-related jobs or academic positions). This information will be made available as a Google Spreadshee...
docs.google.com
November 11, 2025 at 12:11 PM
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.
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.
Sounds like it's from a bad sci fi movie: Bucky built a quantum transducer to travel to the fifth dimension.
November 10, 2025 at 7:12 PM
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.
Sounds like it's from a bad sci fi movie: Bucky built a quantum transducer to travel to the fifth dimension.
Reposted by Lance Fortnow
A wonderful puzzle rescued from oblivion.
www.theguardian.com/science/2025...
www.theguardian.com/science/2025...
Can you solve it? Two dead at the drink-off – a brilliant new lateral thinking puzzle
Who poisoned who?
www.theguardian.com
November 10, 2025 at 7:19 AM
A wonderful puzzle rescued from oblivion.
www.theguardian.com/science/2025...
www.theguardian.com/science/2025...
The death of the last grandchild of a former president drives Bill into action.
A Presidential Trivia Question, how I tried to solve it
A friend of mine told me that in the last six months, the last grandchild of one of our former presidents (who had already passed aw...
blog.computationalcomplexity.org
November 10, 2025 at 12:43 PM
The death of the last grandchild of a former president drives Bill into action.
Reposted by Lance Fortnow
Hopefullly they also include test of space awards.
Computational Complexity Conference launches its first test of time award. Nominations due by March 2.
computationalcomplex...
computationalcomplex...
November 9, 2025 at 4:28 AM
Hopefullly they also include test of space awards.
Computational Complexity Conference launches its first test of time award. Nominations due by March 2.
computationalcomplex...
computationalcomplex...
November 8, 2025 at 10:59 PM
Computational Complexity Conference launches its first test of time award. Nominations due by March 2.
computationalcomplex...
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.
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.
Preprint site arXiv is banning computer-science reviews: here’s why
Nature - The repository is taking steps to tackle a surge in low quality, AI-generated content.
doi.org
November 8, 2025 at 6:29 PM
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.
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.
The Complexity Argument for Capitalism
We're seeing an attack on capitalism on both ends of the political spectrum with with the election of Democratic Socialist Zhoran Mamdani as...
blog.computationalcomplexity.org
November 6, 2025 at 8:48 PM
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?
Palantir Thinks College Might Be a Waste. So It’s Hiring High-School Grads.
Tech company offers 22 teens a chance to skip college for its fellowship, which includes a four-week seminar on Western civilization
www.wsj.com
November 4, 2025 at 8:36 PM
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.
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.
Did Euclid exist? Is it okay to quote people that did not exist?
The following excerpt from Abrahim Ladha's comment on Lance's post about AI and intro theory caught my attention: ------------------------...
blog.computationalcomplexity.org
November 4, 2025 at 3:50 PM
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.
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
Venkatesan Guruswami selected as director of the Simons Institute for the Theory of Computing
We're delighted to announce that following a worldwide search, Venkatesan Guruswami has been selected as directo
simons.berkeley.edu
November 1, 2025 at 9:06 PM
Venkatesan Guruswami selected as director of the Simons Institute for the Theory of Computing
Reposted by Lance Fortnow
Nonuniformity in circuits always seemed to me to be more of a technicality, but artificial intelligence points to its surprising power.
AI and the Power of Nonuniform Circuits
The advances in artificial intelligence have changed the way we think about computing. For today's post, how nonuniformity plays a much larg...
blog.computationalcomplexity.org
October 29, 2025 at 10:10 PM
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
blog.computationalco...
1/2
AI and Intro Theory
This fall, for the first time at Illinois Tech, I'm teaching Introduction to Theory of Computation. While I've taught a variation of this co...
blog.computationalcomplexity.org
October 27, 2025 at 8:05 PM
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
blog.computationalco...
1/2
Bill doesn't care.
Bill's Bad Advice
I sometimes give the following advice for research which I label Bill's Bad Advice . We will later see who it might be good advice for. Spo...
blog.computationalcomplexity.org
October 27, 2025 at 1:03 AM
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...
Details: acm-stoc.org/stoc202...
CFP: acm-stoc.org/stoc202...
October 25, 2025 at 5:16 PM
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...
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.
AI and Intro Theory
This fall, for the first time at Illinois Tech, I'm teaching Introduction to Theory of Computation. While I've taught a variation of this co...
blog.computationalcomplexity.org
October 23, 2025 at 1:43 PM
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.