Does ChatGPT really help programmers?

 
BILL: I honestly do not know whether ChatGPT will make programmers more productive. (I am not touching question of whether it puts programmers out of work. That's a problem for Future Bill.) Who can I ask? I found two people who disagree on the issue:

Alice who supports developers in industry. She doesn't write code full time now, but she has written plenty before. She thinks that NO, ChatGPT and LLMs DO NOT help programmers.

Bob is a  friend of a friend who writes code for a living and owns a small software/database company. He thinks YES, ChatGPT and LLMs DO help programmers.

I asked Alice and Bob to discuss the issue over email and make a blog post out of it, or have ChatGPT do it for them. Below is the result.

---------------------------------------------

ALICE: Recently I needed to add CSV import to my apps. The columns in the file needed to be optional and allowed in any order. I  could have figured it out myself but I thought Why not let an LLM do the boring part?

The first two answers it gave me ignored my requirement on the columns. If a human had done this, I would have asked them whether they had read what I wrote. On the third try, it produced something
reasonable. But in the end I went with a different approach anyway.

So yes, the LLM gave me code---just not the code I wanted. Sort of like ordering a salad and getting a smoothie: technically vegetable, but not what I asked for.

BOB: ALICE; you’re basically proving my point for me. You gave the model a fuzzy spec, it gave you fuzzy code. That’s not an indictment of LLMs — that’s just computers doing what computers have done for 70 years.

When I give an LLM a tight spec, it behaves. When I’m vague, it hallucinates. Honestly, that’s not that different from hiring a junior dev, except that the LLM doesn't steal your sparkling water out of the refrigerator or ask what CRUD stands for.  (Create-Read-Update-Delete)

BILL: I recommend keeping a small refrigerator in your office rather than use a communal one.

BOB: Good idea! Anyway, this (writing code, not giving advice on cutting down office theft) is exactly why LLMs save me time: I can hand them the dull bits: scaffolding, boilerplate, adapters — all the stuff I can write but would rather not spend a day on when a decent model will spit out 80% of it in 20 seconds.

ALICE: We tried having an LLM add some error checking to one of my apps. I wanted to put the checks in a plausible place, but it wasn't the best place because it didn't understand that there was another method that already did some of the error checking. It was able to modify a method in a way that was similar to another method it was told to use as a sample. But, I didn't find this too useful. Trying to get it to make such small changes to the code just interrupted my train of thought and required me to spend effort carefully reviewing what it wanted to do.

BOB: I get the train of thought thing — but that’s because you’re trying to use the model as a scalpel. I use it as a bulldozer.

I don’t ask it to make tiny edits inside an existing method; I ask it to refactor an entire 20-year-old unit. That is where it shines.

Recently I refactored code I hadn’t touched since the middle ages. Without an LLM? A week of muttering my ancient comments I’m embarrassed to admit I wrote. With an LLM? Half a day.

It identified the structure, spotted duplications, clarified naming, and turned archaeological dig into Tuesday morning. That’s the sort of productivity gain you don’t shrug off.

ALICE: We had an LLM review one of my apps. Some of what it wrote was correct, but some were just nonsense. It was just writing plausible sounding things, picking bits of my code to justify them, but didn't  understand the code. Its suggestions were vague (e.g., add unit tests), which is the code equivalent of your dentist saying floss more.

BOB: If you ask an LLM to review my app, you’ll get vague motherhood statements. If you ask a human the same Focus only on concurrency issues in this module, or Explain where this user’s error could be triggered based on these logs, it becomes very sharp.

This is, frankly, where it’s scarily good: tracking down where a user-reported issue is probably happening. Humans tell me symptoms; the LLM translates that into “It’s almost certainly in this 40-line cluster over here”, and it’s right far more often than chance. That alone pays for the subscription.

BILL: I've read through your 194 email saga, I still don't know what the upshot is. So, like a court case, each of you give your closing statements.

BOB: LLMs are not magic interns who understand your architecture. They're incredibly powerful amplifiers when you use them properly. For me, the time savings are real — especially in refactoring legacy code, debugging from cryptic user reports, and generating UI scaffolding that would otherwise be tedious.

Do I trust them to invent a brand-new algorithm whole cloth? Of course not — I write NP-Complete solvers for fun. But for 70% of my day-to-day coding, they turn chores into quick wins. And that makes me a more productive programmer, not a lazier one. 

ALICE: LLMs may be helpful for writing small, self-contained chunks of code or for suggesting approaches. But, they do  not understand code. Most of what programmers do requires understanding the code. So, LLMs will be of little, if any benefit, to most competent programmers. Coaxing LLMs to produced something useful takes more time than people realize.

Or as I like to put it, they're great at writing code-shaped objects, not actual code.

BILL: Thank you. I am enlightened. And don't forget to floss before brushing.

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 part of the talk he argued that if AI makes writing technical papers easier, researchers will write up small results that they wouldn't have bothered with before. He thought having a swarm of minor result papers was a bad thing but I'm less sure. Let's get the little results out there. We'll sort them out later, probably with the same AI that helped write them in the first place.

In my career I've had several little theorems in complexity. They should never get into any respectable conference, so what do you do with them? Sometimes I stick them in a sort-of-related paper, in a blog post, or let someone else mention the theorem. Too often the results just don't get written. Did you know that finding an \(S_2^p\) witness is equivalent to TFNP^NP? I never found a good place to put it.

Fermat himself never published his "little theorem" from last week's post. He put it in a letter to his friend and fellow mathematician Bernard Frénicle de Bessy. Euler would first publish the proof nearly a century later.

The journal Information Processing Letters used to play the role of publishing moderately interesting research but like most Elsevier journals has long lost its cachet. You can stick little theorems on arXiv, though that still requires writing them up. Using AI to mostly write up results is still frowned upon, but maybe we should make exceptions for papers that wouldn't normally get written. 

Once I used the fact that P^PP = P^#P and a referee asked for a reference. The proof isn't hard, just a simple binary search, but I couldn't find anyone who first proved it. Not by Valiant who introduced #P or by Gill who defined PP. Eventually I cited a paper by Toda, who had mentioned the result but didn't claim it. Perhaps whomever proved it first never thought to write it up assuming that it was already well known. 

Factoring Carmichael Numbers

Carmichael Numbers are the bane of probabilistic primality algorithms. You have to go through extra steps just to handle these relatively rare numbers. But did you know that the Miller-Rabin algorithm not only determines the compositeness of Carmichael numbers but can actually find non-trivial factors? Apparently none of the AI models I tried did either. Feel free, Google, OpenAI and Anthropic, to train on this blog post.

Let's start with Fermat's little theorem, not as big as his "last" one but one where we know he had a proof. It states that for any prime \(p\),  \(a^p \equiv a\bmod p\) for all integers a. That suggests a primality test, if you can find an \(a\) such that \(a^m \not\equiv a\bmod m\) then you know \(m\) is not a prime. For example, since \(29^{143}\equiv 35\bmod 143\) then \(143\) is not prime. 

The set of \(a\) such that \(a^m \equiv a\bmod m\) forms a subgroup of \(Z_m^*\) (the numbers \(b\) less than \(m\) with gcd\((b,m)=1)\), if there are any integers \(a\) that fail the test then at least half of  the \(a\) will. So you could just choose a random \(a\) and check if \(a^m \equiv a\bmod m\). That would work for all the composites where there is an \(a\) such that \(a^m \not\equiv a\bmod m\). Alas there is a relatively rare set of composites, known as Carmichael numbers, for which  \(a^m \equiv a\bmod m\) for all \(a\) co-prime to \(m\). The first few Carmichael numbers are \(561\), \(1105\), \(1729\) and \(2465\). For example \(29^{561}\equiv 29\bmod 561\).

So probabilistic primality tests need to account for these Carmichael numbers. Let's look at the Miller-Rabin test. 

• If \(m\) is even, output "prime" if \(m=2\), composite otherwise.
• Pick \(s\) and odd \(d\) such that \(m-1=2^sd\).
• Pick random \(a\) between 2 and \(m-2\). If gcd\((a,m) \neq 1\) return composite.
• Let \(x = a^d\bmod m\)
• Repeat s times
• Let \(y=x^2\bmod m\)
• If \(y=1\) and \(x\not\in\{1,m-1\}\) then composite.
• Let \(x=y\)
• If \(y=1\) output "probably prime" otherwise "composite"
  

Here's the kicker. If the Miller-Rabin test says "composite" before the last step, you'll get a factor. Note that \(y-1=x^2-1=(x-1)(x+1)\equiv 0\bmod m\). But since neither \(x-1\) or \(x+1\) is a multiple of \(m\), the greatest common divisor of \(x-1\) and \(m\), as well as the gcd of \(x+1\) and \(m\) will give you a non-trivial factor of \(m\).

For example if we start with \(m=561\) and \(a=29\), we have \(d=35\) and \(s=4\), \(29^{35}\bmod 561=164\) and the \(y\)'s will be \(592,463,67,1\). For \(x=67\), the gcd of \(x-1=66\) and \(561\) is \(33\) and the gcd of \(x+1=68\) and \(561\) is \(17\). \(561=33\times 17.\)

Finally Carmichael numbers will never say "composite" in the last step, so the Miller-Rabin algorithm will always find a factor when it says "composite".

In 2002, Agrawal, Kayal and Saxena gave the first provably polynomial-time algorithm for primality. As far as I know AKS doesn't factor Carmichael numbers and there isn't any known deterministic polynomial-time algorithm finding non-trivial factors of Carmichaels, though if the generalized Riemann hypothesis is true, you need only try the first \(O(\log^2 m)\) \(a\)'s in the Miller-Rabin test. 

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 Test-of-Time awards in computer science.

Below is a list of various computer science Test-of-Time awards, along with their

eligibility requirements.

1) IEEE Visualization (VIS) Test of Time Award, see here.   VIS=Visualization.  Their 2023 award page says:

Papers are selected for each of the three historic conferences (VAST, InfoVis, and SciVis). ... 

This year VAST gave out a 10-year test of time award, InfoVis a 10- and 20-year award, and SciVis a 13, 14 and 25 year award.

2) SC Test of Time Award, see here. SC=Supercomputing Conference.  Their site says:

Papers appearing in the SC Program 10 to 25 years prior are eligible.

3) CIKM Test of Time Award, see here.   CIKM=Conf. on Information and Knowledge Management.  Their page states:

The Test of Time Award is given for CIKM papers published at least ten years ago.

3) ACM SIGCSE Test of Time Award, see here. SIGCSE = Special Interest Group on Computer Science Education.  ACM=Association for Computing Machinery. The name is from the era when computers looked like angry filing cabinets.  The ACM SIGCSE Test-of-Time page states:

The award recognizes an outstanding paper published in the SIGCSE community. 

 Note that this is broader than just their conference. Good!

4) LICS Test of Time Award, see here. LICS=Logic in Computer Science.  Their award page says:

The LICS Test-of-Time Award recognizes a small number of papers from the LICS proceedings from 20 years prior.

5) STOC Test of Time Award, see  here. STOC = Symposium on Theory of Computing.  Their page states:

There are three awards---papers presented at the STOC conferences in 10, 20, or 30 years ago [they later say there is some flexibility on that]. 

6) FOCS Test of Time Award, see  here. FOCS stands for Foundations of Computer Science.  Their page states:

The awards recognize papers published in the Proceedings of the Annual IEEE Symposium on FOCS. [From elsewhere on the page they have three categories: papers 10-years ago, 20-years-ago, and 30-years ago, but they have some flexibility with that.]

7) SIGecom Test of Time Award, see here. SIGecom = Special Interest Group---Economics and Computation.  Their page states:

...must have been first published in an archival journal or conference proceedings 10–25 years before. At least one author must not be dead. [A surprisingly nontrivial constraint in a Test-of-Time award.]

I think this is the only award on this page that stated the not-dead criteria explicitly.  Are people in Economics and Computation publishing papers into their 90's? While in hospice care?

8) NeurIPS Test of Time Award, see here.  NeurIPS = Neural Information Processing Systems.  I couldn’t find an eligibility description, so I asked ChatGPT, which confidently stated:

Yes—the paper must have been published in NeurIPS at least 10 years ago. 

If this is wrong, please let me know. ChatGPT is sometimes confident the way undergraduates are confident before seeing the homework solution.

9) CCC Test of Time Award, see here. CCC=Computational Complexity Conference. Their page states:

Eligible papers are those that appeared in CCC (or Structures, pre-1996) at least 10 years ago. 

------------------------------------------------------------------------

These awards raise some questions:

1) Why tie eligibility to a conference?  Suppose Abisola proves P ≠ NP and publishes it in Annals of Mathematics.  Under many of these rules, she would be ineligible for most theory Test-of-Time awards.

CON: Important results may not appear in the “right” conference or any conference at all.

PRO: None. Absolutely none.  Why is it done?  To publicize the conference and provide a nice ceremony venue.  These are not strong intellectual reasons. (I had a nastier comment about this but ChatGPT convinced me to be more polite.)

My proofreader brought up the following:

a) Who will give out the award? Answer: An organization like the ACM, and it DOES NOT need to go to an ACM conference.

b) How to limit what papers are eligible? Any paper that was in a conference or journal (though see item 3 below). That seems like a rather large set of papers to consider; however, after 10 years we DO know which papers stood the test of time. As an example- when Lance made his best theorems of the decade lists he did not pay attention to which venue the result appeared in.

2) Why the 10–25 years ago window?  I understand waiting 10 years—time needs time.  But why exclude older papers?  What if the paper Some Connections Between Bounded Query Classes and Nonuniform Complexity (STRUCTURES/CCC 1990) suddenly becomes important? Too bad: it aged out, like a carton of milk.

Are there examples of papers that became important many years after they were published?

I have one sort-of example: Google AI Overview says

The permanent of a matrix was first introduced independently by Cauchy in 1812 and later independently rediscovered by Binet in 1812. [The identical years makes me suspect, and also makes the notion of ``later'' rather odd- Did Cauchy do it in February and Binet in June?]

The permanent became much more important after Valiant, in 1979, showed that it was Sharp-P-Complete. So perhaps Cauchy's paper should get a test-of-time award.

Fun Fact: The Wikipedia entry on The Permanent (see here) does not mention Valiant, though there is a separate Wikipedia entry on Computing the Permanent (see here) that does.

3) Why require publication in a journal or conference at all?  Suppose Perelman proves P ≠ NP, posts it on arXiv, and never submits it anywhere.  Perelman did just that with his proof of the Poincare Conjecture, and that was good enough for a Fields Medal.

This touches on the much broader---and increasingly relevant—question: What is the future role of journals and conferences in the age of arXiv?

4) (Bonus question): Is there any real difference between the STOC conference and the FOCS conference in terms of the scope of the papers?  Was there ever?  I would guess no and no. Maybe some of my older readers can tell me, unless they are too busy writing papers in Economics and Computation. 

5) Another proofreader pointed out that it would be a good idea to live up to the title of this post, Test of Time Awards: A Good Idea but, and say why they are a good idea instead of bitching and moaning about eligibility. Good Idea! Some thoughts:

a) They might encourage researchrs to aim for deep contributions, not just fashionable ones. I doubt this is true since I doubt authors think about which award they might win.

b)  They reward long-time impact over short-term excitement. Is it much of a reward? How do they benefit the recipient? I ask non-rhetorically. 

c) They are an objective record of subjective opinion.  Useful for historians!

 

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 large online Artificial Intelligence course. Students would ask questions to an online forum, and fellow students and TAs would answer these question. Unbeknownst to the students, Ashok had an AI system answer questions from the forum with the moniker Jill Watson (it was built on technology used for Watson's Jeopardy win). Jill answered questions about administrative issues in the class, so well that most students were surprised it was an AI system. Goel still needed human TAs to handle questions about course content.

In the talk Goel made comments ahead of his time.

Today, we have classes with a hundred or more students, and few get personal attention. We even have massive open online courses, where students learn from prerecorded video lessons. Some of these classes attract 100,000 students, but only 10 percent or fewer complete them—because of the lack of teaching assistance and personal attention. 

This raises a fundamental issue: can we have personal attention at scale? What if we could give personal attention to every student, when and how they needed it? That would create an educational revolution—because learning and teaching would become personal again...I envision a future where everyone has access to AI teaching assistants like Jill Watson—anytime, anywhere, for any task. A future where education is affordable and accessible to all, yet still personal and fun. 

Fast forward to today and AI assistants can answer questions about course content pretty well for nearly every undergraduate course in all disciplines. A well-trained AI tutor outperformed in-class active learning. While I haven't seen formal studies, students seem to go to ChatGPT before reaching out to TAs, instructors or their fellow students. AI can grade assignments and exams. 

Teaching assistants still have an important role to play. They teach recitation sections and run student labs. A great TA can provide a human connection with a student that no computer could. A teaching assistantship gives important training to students who might become academics, as well as providing an important funding mechanism, especially in the humanities and social science which has limited grant support for graduate students. But in a time of budget constraints at many institutions, how can we argue for the same TA support at the levels we had back in 2016?

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 away) died.

I tried to  deduce who it was without checking the web directly. For example, I  looked up when various presidents were born to narrow it down, but try not to search for the answer itself.

I could look this up easily. However, by spending time thinking about it and exploring related questions, I might learn things I  didn’t know before.

Things I care about? Maybe.

I now have a lot of white space, so you can think about the answer yourself and perhaps make a guess, then my reasoning process and the answer.

Before answering, I’ll walk through the reasoning I used for my educated guess.
Assume the president was born in year x.

ADDED LATER: In the original version of this post (and its still there) I would make comments like: 

                           Warren G. Harding- why is the G always mentioned.

A commenter pointed out that middle names and initials are an American thing. This made me wonder why some of them didn't use their middle initial. Hence I have ADDED information about that. I won't bother writing ADDED LATER for those late adds. 

END OF ADDED LATER

Assume the president’s youngest child is born in approximately year x+35.

Assume that child’s youngest child is born in approximately year x+70.

Assume the grandchild lives 80 years, so dies in approximately year x+150.

Then x+150=2025, so x=1875.

Since this is an approximation, I looked at all presidents born between 1850 and 1900. The website I consulted tells us the answer. What would we do without the internet? (Maybe spend more time offline tightening our bounds on the polynomial van der Waerden numbers.)
Here are all the presidents who were born in a year in [1850,1900].

Theodore Roosevelt — born 1858. Formal name: Theodore Roosevelt Jr. No middle name. 

William Howard Taft — born 1857. He seems to have his full name mentioned. Why? 

Woodrow Wilson — born 1856. Formal name: Thomas Woodrow Wilson. So it would be impossible to use a middle initial unless you do what David Dwight Eisenhower did and swith the two names, so then he would be Woodrow T. Wilson. 

Warren G. Harding — born 1865

Calvin Coolidge — born 1872. Formal name: John Calvin Coolidge Jr. Similar to Woodrow Wilson.  Cal's dad was John Calvin Coolidge Sr.  Naming your kid after yourself, including the middle name, coud be a mistake, see here.

Herbert Hoover — born 1874. Formal name: Herbert Clark Hoover. I am surprised he wasn't called Herbert C. Hoover. Maybe Herbert Hoover was better because its alliterative. 

Franklin D. Roosevelt — born 1882

Harry S Truman — born 1884 (There really is no period after the S. Both chatty and Wikipedia get that wrong.)

Dwight D. Eisenhower — born 1890 (born David Dwight Eisenhower; he preferred to be called Dwight).

When I was asked the question, I guessed Harry S. Truman. I was wrong.

In fact, none of the presidents on that list is the one. 

The correct answer is John Tyler, who was born in 1790.

My rule-of-thumb assumptions (35 years to have a child; an 80-year lifespan) were  large underestimates for this case. John Tyler had sixteen children. The third-to-last was Lyon Tyler, born in 1853 — John Tyler was 63 at the time, which is 28 years more than my estimate of 35. Lyon Tyler had six children; the second-to-last was Harrison Tyler, born in 1928 — Lyon was 75, which is 40 years more than my estimate of 35.

(In 1840 William Henry Harrison and John Tyler were elected Prez and Veep. WHH died after giving his inaugural speech in the cold rain, and Tyler became president. Lyon Tyler names his son Harrison. My thought was: Did Lyon name his son after WHH? I asked Google 

Why did Lyon Tyler name his son Harrison? 

The AI Overview said:

Lyon Tyler named his son Harrison because his own mother, Julia Gardiner, was a member of the Harrison family of Virginia, making Harrison a great-grandson of both President John Tyler and William Henry Harrison, the president whom John Tyler succeeded. Naming his son Harrison was a way for Lyon Tyler to honor the family connection to both presidents, particularly the presidential connection. 

Thats not quite right- Harrison is John Tyler's grandson, not great-grandson. 

I didn't know that John Tyler's grandchild was named Harrison.

I didn't know that John Tyler's grandchild was also related to WHH.

)


Harrison Tyler died in 2025 at the age of 96, which is 16 years more than my estimate of 80.

So my point (do my posts need a point?) is that I made an approximation but was still way off. John Tyler is an outlier, which is hard to account for.

Let’s say I assumed 60-year-old fathers and the grandson lives to 90. Then we would have:

x + 210 = 2025
x = 1815

This is an approximation, so I would look at presidents born between 1790 and 1840:

John Tyler: 1790. No middle name. 

James K. Polk: 1790. Why is the K always mentioned?

Zachary Taylor: 1784. No middle name. 

Millard Fillmore: 1800. No middle name. 

James Buchanan: 179. He never had kids. That’s just as well, since his children would have had the stigma of their father being one of the worst presidents of all time by most accounts.

Abraham Lincoln: 1809. Born February 12, 1809 — the same day and year Charles Darwin was born. No middle name. 

Andrew Johnson: 1808. No middle name. 

Ulysses S. Grant: 1822.  Born Hiram Ulysses Grant, but he didn’t like that the initials were H.U.G.

Rutherford B. Hayes: 1822. Why is the B always mentioned?

James Garfield: 1831. James Abram Garfield. I sometimes see the A initial and sometimes not. 

Chester Arthur: 1829. My Darling’s favorite president — really! Formal name Chester Arthur which I have seen written, though not as much as the others. Perhaps I just didn't notice him as much as my Darling did. 

Grover Cleveland: 1837. Formal name: Stephen Grover Clevelant. 

Three points:

1) When I picked 60–60–90, I did not know that John Tyler would actually make it onto the list.

2) He just barely made the list.

3) I would not have picked 60–60–90 unless I had already learned that 35–35–80 was far too small.

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 mayor of New York, and Donald Trump trying to direct the economy through tariffs, less independency of the Federal Bank and partial government control of companies such as a nearly 10% ownership of Intel and the "golden share" of U.S. Steel.

Now I'm not an economist and there are many arguments for and against socialism and capitalism, especially in their purest forms. I want to focus on the complexity of the economy. Let's start by considering rent control.

It starts with the worthy goal of preventing people from having to leave their apartments because of rising rents due to market demand. So you limit the rent increases and the ability to evict current residents. But this could cause landlords to cut back on improvements, not prioritize service and repairs, or build new properties to increase the supply. So you have to give landlords incentives to do these things, leading to other issues which leads down a rabbit hole. I saw extreme rent control in Berkeley in the 1980s and a lack of available housing forced me to live 13 miles away. 

That's just rent control in a single city. Other attempts to control the economy will lead to unexpected inefficiencies and you can't predict markets enough to catch them.

The 1920 essay Economic Calculation in the Socialist Commonwealth by Ludwig von Mises argued that market prices give critical information for companies and individuals to make decisions. I think of it like a circuit, where the prices are values of intermediate gates so that we can have simple operations at every level leading to a very complex behavior in the aggregate, much like a neural net today. Frederick Hayek went further in his 1945 essay The Use of Knowledge in Society that a center planner couldn't adapt with the speed of change in the markets. 

Could today's neural nets replace the need for these intermediate pricing and adapt quickly? It's really a combination of the two, many companies are using sophisticated machine learning models that lead to more accurate pricing, adding to the efficiency of markets. 

Capitalism has its challenges: Companies can shrink or close, people can lose their jobs and we need good safety nets. Government has a role to protect safety, enforce contracts and provide services and some control where competition doesn't scale, like utilities and pubic transportation. Government also has a role in promoting public goods including education, scientific research and national defense. 

While neither Mamdani or Trump want anything close to complete government control of the economy, I still worry that even their limited influences will hurt innovation and in the longer run hurt the very people these policies are meant to help. 

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:


---------------------------
BEGIN EXCERPT

Not just with AI, but in theory and math courses, there have always been Bart Simpson
level questions by students of the form

"Why do I need to know this?

like

Why do I need to know my times tables when the calculator does this for me?

There has never been a good answer because these students already do not have an open mind.
Euclid was asked such a question once and said something like

give him a penny so he may feel like he earned something for what he learned.

END EXCERPT
-----------------------------------

He gives a quote by Euclid.

1) I have heard that Euclid might not have really existed.

2) I have never heard that quote.

I asked Abrahim Ladha if he had a source for the Euclid quote.

I never go a response.

I asked chatty:

        What is the historical evidence that Euclid existed?

and also

        Did Euclid say give him a penny so he may feel like he earned something for what he learned?

The answer to both questions are below. The bottom line is that

1) Euclid might not have existed.

2) The idea underlying the quote is attributed to him. The exact quote is modern rendering. 

Should Abrahim have consulted chatty before making his comment.

1) YES, it's important to make sure your facts are correct.

2) NO, his point is still valid. (That is a slippery slope.)

----------------------------------------
BILL: What is the historical evidence that Euclid existed?

That’s a great question — and a surprisingly tricky one.

Short answer

There is no direct historical evidence that Euclid (often called Euclid of Alexandria) existed
as an individual in the way we can verify the existence of, say, Archimedes. What we “know”
about Euclid comes almost entirely from later sources, not from contemporary records.

The evidence we do have

1)
Type: Ancient testimonies

Source: Proclus, Commentary on the First Book of Euclid’s Elements

Date: ca. 450 CE

Note: Written about 700 years after Euclid’s supposed lifetime. Proclus says Euclid lived
in the time of Ptolemy I (reigned 323–283 BCE) and taught in Alexandria. This is our main source.

2)
Type: Mentions by other ancient authors

Source: Pappus of Alexandria (4th century CE), Diogenes Laërtius (possibly), and others

Date: 200–600 years later

Note: These references repeat information similar to Proclus’s account — that Euclid compiled
the Elements and worked in Alexandria.

3)
Type: Mathematical evidence

Source: The Elements and other works attributed to Euclid (Data, Optics, Phaenomena, etc.)

Date: ca. 300 BCE?

Note: These texts show a unified style and method, suggesting a single organizing mind
(or school). But there is no personal or biographical detail inside them.

4)
Type: Absence of contemporary evidence

Note: There are no letters, inscriptions, or administrative records naming Euclid. No ancient
biography (unlike Archimedes or Apollonius).

Scholarly interpretation

Traditional view: There was a historical Euclid, a mathematician who worked in Alexandria
around 300 BCE and compiled earlier Greek geometry into the Elements.

Skeptical or revisionist view: “Euclid” may have been a collective name for a team or a
school of mathematicians in early Hellenistic Alexandria, much like “Hippocrates” in medicine.

The Elements itself is consistent in style, so even if multiple people contributed, it was
edited or systematized by someone with extraordinary coherence and rigor.

In summary

There is no direct documentary or archaeological proof that Euclid existed as an individual,
only later testimony and internal evidence from the mathematical works. Historically, most
scholars accept that there was a person — or at least a leading mathematician — behind the
name “Euclid,” but his life remains almost entirely unknown.
---------------------

BILL: Did Euclid say

`give him a penny so he may feel like he earned something for what he learned.'

ChatGPT said:

The quote you’re referring to — something like “Give him a penny so he may feel he has learned
something” — is attributed to Euclid, but not in those exact modern words.

It comes from an ancient anecdote recorded by Proclus (a 5th-century commentator on Euclid) in
his Commentary on Euclid’s Elements. The story goes like this:

A student, after learning the first theorem of geometry, asked Euclid,

“What shall I get by learning these things?”

Euclid called his slave and said,

“Give him a penny, since he must make gain out of what he learns.”

In Greek, it’s roughly:

“Δός αὐτῷ ὀβολόν, ἐπειδὴ κερδαίνειν δεῖται ἀπὸ τῶν μαθημάτων.”

So your paraphrase captures the spirit of the anecdote — Euclid was mocking the idea of
studying geometry for material reward — but the exact wording

“give him a penny so he may feel he earned something for what he learned”

is a modern retelling, not a direct quotation.

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 larger role than I previously believed.

First, some background. Circuit complexity gives a different, more combinatorial, way to look at computation. Instead of viewing algorithms as step-by-step programs, circuit complexity captures computation as fixed hardware, gates wired to compute a function of their inputs.

Every polynomial-time computable language L can be computed by a family \(C_0,C_1,\ldots\) of polynomial-size circuits, where \(C_n\) has n inputs, the number of gates of \(C_n\) is bounded by \(n^c\) for some \(c\) and \(x=x_1\ldots x_n\) is in L iff \(C_n(x_1,\ldots,x_n)\) outputs 1.

The converse isn't true, there are languages L that have polynomial-size circuits that you can't compute in polynomial time, because each \(C_n\) might not have any relation to \(C_m\) for \(n\neq m\). We can get the equivalence by adding a uniformity condition, that there is some easily computable function \(f\) with \(f(1^n)=C_n\). Or we can keep the nonuniformity to define a larger class called P/poly. 

In practice, nonuniformity rarely helps. We can hide randomness in the nonuniformity but we could likely also use pseudorandom generators to the same effect. Nonuniformity was more a technicality that we had to deal with instead of something that seemed to give circuits significantly more power.

Until we reached this new age of AI. A machine learning model like a neural net goes through a lengthy training process to learn its weights, the training optimized offline. The learned weights become the nonuniform circuits, as technology improves and we create larger retrained circuits, the weights change as well.

We typically use the complexity class TC\(^0\), languages accepted by poly-size, constant-depth with threshold circuits as a rough theoretical model for neural nets. For nonuniform TC\(^0\) we cannot prove any significant upper bounds, we can't even show NEXP, nondeterministic exponential time, cannot be computed by nonuniform TC\(^0\) circuits. And while computing NEXP or even P in TC\(^0\) would be incredibly surprising, these advances in artificial intelligence tell us these nonuniform circuits are far more powerful than we would ever have expected. 

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. Spoiler alert: the number of people for whom it is good advice is shrinking but might include Lance especially now (see his post about stepping down from admin, here).

When you come across a possible research topic or problem, or have some idea,  and are wondering if you want to pursue it,  here is my bad advice: 

1) DON"T  CARE if anyone else cares. If YOU care then that is enough to at least get started. 

2) DON"T  CARE if it has the potential for a published paper. FIRST do the work then, if you feel like it, look for a good venue. You might not bother if posting to arxiv or making an open problems column out of it or a (guest) blog post out of it is  a good endpoint.  (I run the SIGACT News Open Problems Column- feel free to contact me if you want to submit one.) 

3) DON"T CARE if it has practical implications. 

4) DON"T  CARE if you can get a grant for it. With the current state of the NSF this advice may soon become irrelevant. 

5) DON"T  CARE if someone else already did it (though at a later stage you should check on this). Even if you work on it and find someone else did it, you will have LEARNED about the problem through your efforts. You might then want to do a survey for your own benefit to consolidate your  knowledge. 

Why should you NOT CARE about any of these things? Because they get in the way of actually DOING something.  

Here are two examples of when this approach WORKED and one where it DID NOT WORK, though both classifications might depend on your definition of WORKED. 

WORKED: My work on Muffins. All I wanted was to get some High School and Undergraduate Projects out of it. I ended up with a book on it which made me twenty dollars last year! More to the point, I learned a lot, as did my co-authors and I am happy with the book. The co-authors were Undergraduates so my dept put me up for a mentoring award (I have other credentials as well). I did not win, but I got a nice letter saying they had many qualified applicants. OH- it didn't say if I was one of them. 

WORKED: I have had many Ramsey Projects where a High School Student codes stuff up and learns some Ramsey, some coding, and gets the experience of research. Sometimes they do a survey paper or open problems column. We both learn A LOT from this and the student gets a good letter from me. Do they do something NEW? Publishable? No, though some surveys and open problems columns have come out of this.  I DO tell them ahead of time that the work is unlikely to lead to original results (and hence unlikely to be good for a science competition).   

DID NOT WORK: See this blog post here about the math and here about finding out that the problem we were working on was already known and more was known than we thought. I didn't mind this, but one of the authors did. 

Note that WORKED and DID NOT WORK also depend on your goals. 

For whom is this bad advice? Good advice? 

1) It was always bad advice for young assistant professors who need to get papers and grants to get tenure. 

2) Hypothetically, once you get tenure you have job security and hence can change fields or follow my bad advice without consequences. But with grants and salary and teaching load issues, this is less the case. Perhaps I am nostalgic for a time that never was.

3) High School Students were my main audience for bad advice. It's not as important for them to get papers out as for (say) assistant professors. But even this is changing. Colleges are getting more competitive. And HS students may well want a project that can lead to Science competitions. I am not going to say things were better when I was a kid but instead pose non-rhetorical questions:

a) Are high school students getting into research earlier than they used to? I am sure the answer is yes.

b) Are we losing the safe space where a high school student can just learn things and do things and not worry so much about if it's publishable?  Yes, but I am not sure how widespread that is.

c) If we are losing that safe space, is that a bad thing? 

d) Points a,b,c apply to ugraduates who want to go to graduate school more than for high school students who want to go to college. 

4) Full Professors may have more freedom to follow my bad advice. Lance is looking for things to do now that he is no longer a dean, and indeed, is back to being a teaching-and-research professor. So he might follow my advice. However, he actually cares if people care about his work. He does not have to follow all of my advice, but he can follow some of it. 

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 course a couple dozen times, I last taught this class Spring 2016 at Georgia Tech. Intro Theory is a course whose main theorems don't change but it feels different in the AI era.

Here are the big and little things for me.

NP as a Hard Problem?

Garey and Johnson's classic 1979 book on NP-completeness had this famous cartoon.

While the employee couldn't prove that a certain NP-complete problem didn't have a quick solution, at least he could tell his boss that all these famous computer scientists have also tried and failed. The implication is once you show a problem is NP-complete, you should give up. But these days, we have great tools that can often solve or approximate well many practical instances of NP-complete problems such as satisfiability, mixed-integer programming and traveling salesman. NP-completeness is no longer an ending point to give up, but a starting point to try other approaches.

Computation is Hard to Understand

Rice's theorem tells us we can't understand anything about the language a Turing machine computes in general. We can't even tell if a machine halts on blank tape. But for most well-designed programs, we knew how they worked, or at least how they were supposed to work if correctly implemented.

With machine learning, we now have neural nets that we cannot understand how they compute what they do. And like Turing machines, for the most part, all we can do to understand how they work is to look at their input/output behavior.

New Theorems

I first taught this course not long after Neil Immerman and Robert Szelepcsényi independently proved that nondeterministic space is closed under complement and it's now a staple in my course. There are more theorems proven since then that I mention, but don't prove, including the PCP theorem, Primes in P, undirected graph connectivity in deterministic log space, and very recently deterministic time \(t(n)\) in \(\sqrt{t(n)\log t(n)}\) space. 

AI in Teaching

I simply can no longer come up with problems that I can expect undergrads to solve that AI can't solve. So I decided to grade homework on completion instead of correctness so students who wanted to try hard wouldn't feel they needed to use AI to get full credit. For exams, in-class proctored with no electronics. I definitely preferred take-home exams; I just cannot do it anymore.

I use AI to help me format lecture notes and check over my homeworks and exams. The students mostly use AI as their first stop for help instead of office hours. For good reason, the latest LLM models know the material in this course pretty well.

I did manually grade the midterms but for fun asked AI to grade a few of them and its scores were similar to mine.

It won't be long before AI can create videos of me teaching more coherently than I do myself.

Just this week, ChatGPT Pulse out of nowhere gave me a fully formatted intuitive description of the switching lemma for me to teach in class. So I did.

At what point does the AI just take over?

Sept 16, 2025 was Pythagorean Day

     
Several people emailed me that September 16, 2025---written as 9-16-25 in the US---represents the integer side lengths of a right triangle.

9-16-25 is the only such triple that is also a valid date. This kind of mathematical alignment only happens once every 100 years.  The next occurrence will be  September 16, 2125.

Since this is such a rare event, let's explore some more math-themed dates.

1) Pythagorean Triples That Work as Future Dates

Note that 9-16-25 is not a Pythagorean triple; however, 3-4-5 is.

Here are some future  dates that are both Pythagorean triples and valid calendar dates:

March  4, 2105 is 3-4-5

May 12, 2113 is 5-12-13

June 8, 2110 is 6-8-10

July 24, 2125 is 7-24-25 (Darn---July 24, 2025 was recent and I missed it!)

August 15, 2117 is 8-15-17

I think that's it.  Recall that we need the month to be in \(\{1,\ldots,12\}\) and the day to be in \(\{1,\ldots,31\}\) with some exceptions:

Thirty days has September, April, June, and November

All the rest have thirty-one,

Excepting February, fun!

And that has twenty-eight days clear

And twenty-nine in a Leap Year

There are 24 versions of this poem at a website which is  here.

2) Why Didn't Anyone Email Me About Earlier Dates?

I wonder why nobody emailed me on, say, March 4, 2005 (3-4-5).  That's a Pythagorean triple, but maybe it just looked like three consecutive numbers. Oh well.

And what about May 12, 2013 (5-12-13)? That's a really cool Pythagorean triple. Oh well.

3) Other Math-Related Dates Using Month, Day, and Year.
So dates like Pi Day don't count---we want the full date to be interesting mathematically. Side note---I looked up how Pi Day is referred to and its Pi Day, not \(\pi\) day. Probably because not all typesetting systems can easily produce \(\pi\). 

a) Square days:

Dates where the full 8-digit number (MMDDYYYY) is a perfect square.

a1) September  27, 2025 is 9-27-2025 and \(9272025=3045^2\).

Bonus: if you write it as 27-09-2025 then: \(27092025=5205^2\).

a2) Feb 2, 2084 is 2-02-2084 and \(2022084=1422^2\).

b) Palindrome days

b1) March 11, 2030 is 03-11-30 might be the next one.

b2) I was hoping that Feb 2, 2022 (2-2-22) would be a Tuesday (Twosday) but alas, it was not. I asked ChatGPT what is the next year that ends with 22 where Feb 2 is a Tuesday. It gave me incorrect answers four times. When I pointed this out it thanked me for checking its work and then gave me a later incorrect answer. It then gave me a python program that I could run to find out myself. I found out that between the years 1622 to 9922, only looking at years ending with 22, the following pattern happens:

Feb 2, 1622 is a Wednesday

Feb 2, 1722 is a Monday

Feb 2, 1822 is a Saturday

Feb 2, 1922 is a Thursday

Feb 2, 2022 is a Wednesday

Feb 2, 2122 is a Monday

Feb 2, 2222 is a Saturday

Feb 2, 2322 is a Thursday

This pattern repeats as far as I computed, which was 9922. 

I started in 1622 since the Gregorian calendar started in 1582. I stopped in 9922 because of numerical Python issues. I do not know if the pattern goes on forever, or if one of the leap year exceptions will cause that pattern to change. Recall that

Every year divisible by 4 is a leap year. 

EXCEPT if the year is divided by 100 but not 400 then its not a leap year. I have not found any other exceptions on the web but there may still be some. 

b3) I was hoping Feb 22, XX22 (2-22-22)  was sometimes a Tuesday. Here are all the years after 1622,  ending in 22, before 10,000, where Feb 22 is a Tuesday: 2022, 2422, 2822, 3222,...,9622 and I assume in general (2022+400x). Again, the pattern might not hold if there are leap year exceptions I don't know about. 

 

-------------------------------

That is the end of my post. A bonus for my readers: a mini meta post. Long time reader and fellow SUNY Stony brook math major David Marcus (he was class of 1979, I was class of 1980) has been proofreading some of my posts before I post them. Lance suggested I used chatty instead. Instead of using chatty instead, I used chatty and then used David.  David still found mistakes. I give an example here by pointing to all three versions:

Original Version: here

After ChatGPT: here

After David: here (this is not the final version since I read it and made some minor changes)

I may at some later point look at several ORIG/AFTER CHAT/AFTER DAVID and see what errors chatty is not catching. 

Fall Jobs Post 2025

Each fall I try to predict the theory computer science faculty job market to come and give suggestions to those going after them. Get set for a rocky ride, with AI’s disruption of computer science, fiscal stress at universities, and new U.S. policies affecting visas and funding.

In last year's post I wrote

In two years we have gone from nearly all of our computer science graduates getting jobs in the field to many of them struggling to get internships and jobs in the top companies if at all. If the past is any guide, a weak tech job market leads to fewer majors which leads to fewer slots for computer science faculty. We'll start to see these trends this year and they will accelerate quickly if the tech jobs market doesn't recover.

In fact the tech job market for computer science graduates has become much more challenging, ironically as the tech companies have had huge market growth with advances in artificial intelligence. Academia moves slowly, some departments are still catching up on hiring, but that will soon slow. Many computer science departments are adding AI majors and specializations and computer science enrollments over the next few years will be hard to predict.

Computer science is not protected from larger forces. Many universities are facing long-term fiscal challenges, and cuts in research and student funding from the US government aren't helping, leading to hiring freezes at many schools. The demographic cliff, a drop in the US birth rate around the 2008 fiscal crisis, will start hitting colleges in earnest next year. 

The Trump administration has made it more difficult for foreigners to get student visas, leading to a projected drop in incoming international students between 30% and 40%. Recent changes to H1B's, namely the $100K fee an employer would need to pay, may discourage more students who study in the US with the hopes of building a career and a life here. International students, many of whom have gone into computer science, are a major source of tuition for many universities.

Universities would also need to pay the $100K to hire foreigners as faculty and postdocs. Startup packages for new computer science faculty typically run several hundred thousand dollars so this is not out of the question, but schools might be reluctant to pay the $100K in tight fiscal times. These rules may evolve via litigation or administrative reinterpretation. 

Even in a turbulent market, visibility and adaptability matter most. Universities outside the US are trying to take advantage by going after students and faculty. More than ever you should consider positions around the world, especially, but not only, if you are not a US citizen or permanent resident. Other countries have their own challenges, so tread carefully.

On to specific advice for students on the academic job market. 

CATCS maintains a Theoretical Computer Science Jobs posting site. More generally in computer science, there is the CRA Database of Job Candidates and the CRA and ACM job postings. 

And in general make sure you stand out. Areas related to data such as Artificial Intelligence, Data Science and Cybersecurity, will draw the most interest. Best if you can tie your research to those areas, or at least that you are open to teaching in them. Make sure your teaching statement talks about how you will handle AI in the classroom. 

Have a well-designed website with all your job materials and links to your papers. Make sure your Google Scholar, LinkedIn and GitHub (if relevant) sites are accurate and up to date. Make a short video describing your research to a general computer science crowd. Take advantage of all the links above. Network at FOCS or SODA if you can get there. Reach out directly to professors you know at schools you are interested in. And start now.

The Most Common Name in the World is Not Charles Lin. But It Seems That Way To Me.

In 2001 I supervised Charles Lin's Master's Thesis, which was on Private Information Retrieval.

In 2025 I supervised Charles Lin's Master's Thesis, which was on Ramsey Theory.

These are different people. To celebrate the second one's thesis, I took them both out to lunch together. 

A Picture of Charles, Charles, and Bill is here.

I asked ChatGPT about common names.

1) ChatGPT tells me (and I believe them) that the number of people in American named  Charles Lin is between 200 and 900. The answer pointed out that Charles is common and Lin is common but the combination is not common. 

2) ChatGPT tells me (and I believe them) that the number of people named  John Smith is between 25,000 and 40,000. I've heard it's a common name, but I do not know anyone named that. How is that possible?

3)  I predict that people with last name Smith will be reluctant to name their child John because it is so common. Hence this name will decline. However, I made that same prediction 40 years ago. Maybe it did decline TO 40,000.

4) The most common boys' names in 2025 (so far) in the US are, in order:

 Liam, Noah, Oliver, Theodore, James, Henry, Mateo, Elijah, Lucas, William

According to this website here, the five  most common  boys' names in 1960 (the year I was born), in order, are 

 David, Michael, John, James Robert.

James is the only on both lists. 

I don't have the next  five, though I suspect Henry and William would be on it. I also suspect that Liam and Mateo would not be in the top 100.

5) The most common girls' names in 2025 (so far) in the US are, in order:

Olivia, Emma, Amelia, Charlotte, Mia, Sophia, Isabella, Evelyn, Ava, Sofia

(Should they have Sophia and Sofia both on the list? I would say yes but it is odd.)

 According to that same website,  the most common girls' names in 1960 (the year I was born), in order, are

 Mary, Susan, Linda, Karen, Donna. 

 None of the 1960 name are on the 2025 list. I suspect that would still true for the next 10. 

6) When I was in grade school if the teacher said   Quiet down Bill and Lisa the class went quiet. 

7) The most common first name in the world is Mohammad. The most common last name in the world is Wang. Hence the most common name in the world has to be Mohammad Wang. I've asked students to find the flaw in that logic and all 8 Mohammad Wangs in my class found the flaw. Kudos to them! (Darling says I should always tell you when I am kidding. I am kidding. Only 2 of the 8 Mohammad Wangs in my class found the flaw.)

8) (ADDED LATER) One of my readers emailed me the following two items

a) From The Big Bang Theory

Howard: It gets better. Someone has to go up with the telescope as a payload specialist, and guess who that someone is.

Sheldon: Mohammed Lee.

Howard: Who’s Mohammed Lee?

Sheldon: Mohammed is the most common first name in the world, Lee, the most common surname. As I didn’t know the answer, I thought that gave me a mathematical edge.

b) As an interesting aside, I noticed that this semester I have three students named "Luke" and three named "Ben" which made me notice that kids who grew up with the original Star Wars movies would have kids in college around now (but none of my current students are named "Leia")

9) (ADDED LATER)  I HEARD that the name `Barack' was popular when he was president.

I looked it up:

5 babies got that name in 2007

52 babies got that name in 2008

69 babies got that name in 2009

it declined since then.

BAD SCIENCE TIME: The number of babies named Barack increased 10-fold from 2007 to 2008.

TRUE but not significant. 

10)  I hope to supervise at least one more Charles Lin before I retire.

Big Bots Don't Cry

A few comments to last week's post Computers Don't Want suggested that human brains are just advanced computers, yet still possess agency and desires. But are we just Turing machines? I wrote about this question before but let's revisit in the world where artificial general and super intelligence may (or may not) be right around the corner. 

Much of what our brain does, the way we store and retrieve our memories, how we process our senses, how we reason and learn, are very much computational. There is something else, something that gives us an internal view of ourselves, that combined with the computational power of the brain leads to self-awareness, agency, free will, emotions and desires. When I see attempts to give computational explanations for our internal concepts, like the Blums' work on consciousness and free will, I see them capturing the properties we attribute to these concepts, but fail to capture the intuitive notion I have of them. I have some internal capability, a "soul" for the lack of a better name, that allows us to reason about ourselves.

I think of René Descartes and his Meditations on First Philosophy, famous for cogito ergo sum (I think, therefore I am) in the second meditation. Computation and even its execution are mathematical concepts and mathematics lies outside of any physical world. You can't reason from a computational object that it exists. Yet Descartes is able to reason about his own existence. In the sixth meditation, Descartes talks about substance dualism, a separation from mind and body. I view the body as containing the brain, the computational part of our being, but some other entity which, combined with our powerful computational brain, enables us to reason about ourselves and gives us free will, emotions and desires. 

I met a religion professor and asked him about this topic. He mentioned that he had a crying baby sitting next to him on the plane to Chicago. Babies cry for many reasons but sometimes just to be held by their mother or father, a need for companionship. I can imagine a computer doing the equivalent of crying but not the need to do so.

I can't explain how the soul interacts with our brains, I suspect it goes beyond some simple physical mechanism. I can't prove that I have a soul, and while I can't prove the rest of humanity also has souls, I believe they do since otherwise we wouldn't even have concepts like self-awareness. But I don't believe AI models, now or in the future, have something like a soul, and we shouldn't reason about them as though they do.

If you use AI in your work do you brag about it or hide it?

You used AI in your work. Do you hide it or brag about it? 

1) In 2002 there was a movie Simone about an actress who is really an AI.  The Wikipedia entry tells the entire plot. I saved time by reading it in two minutes rather than watching it in 2 hours. I don't think I missed anything.

Key Plot Point: The creator of Simone hides the fact that Simone is an AI. Why hide it? Think of the publicity that would be generated by bragging about it!

The following comment would have been clever in 2002 but is so obvious now that it's banal:

Hiding that it's an AI actress is more unrealistic than having an AI actress. 

Fast Forward to 2025 and into reality: There IS an AI actress named Tilly Norwood (do AIs need last names? Apparently yes.)  She has not appeared in any movies yet but she will be on Instagram and other media soon. Are the creators trying to hide that she is not human? Quite the contrary---they are bragging about it. The Screen Actors Guild is complaining about this, see here. The complaint is that she can't be a real actress since she has no real life experiences to draw upon. If they are saying she won't be a good actress, that's for the studios and the audience and the critics to decide. If a new technology is threatening your livelihood then the argument it's not very good is a terrible argument since it may well be false and is not really what your concern is. 

2) Recently Scott used AI GPT-5-thinking to help him with a proof. Did he hide this fact? Quite the contrary, he pointed it out as an interesting application of AI. See his blog post here.

3) There was a Chemistry Nobel prize, and a Physics Nobel prize, for work done where AI played a role. Did they try to hide that AI was used? Quite the contrary.  See Lance's post on this, here.

4) Do you know of any case where AI or a computer was used and the authors wanted to hide that fact? Aside from  Chess players using a computer, and students using ChatGPT, I cannot. Not for any serious research. (My spellcheck thinks ChatGPT is not a word. This time spellcheck is wrong.) 

5) The opposite has happened: The Mechanical Turk chess-playing "machine". See here.

6) I recently saw the movie I, Robot from 2004. The main human character is against robots and says Can a robot write a symphony? He means this to be a rhetorical question whose answer is no. I counter: can a computer write a movie as dumb as I, Robot? Simone?

Computers Don't Want

I read through the new book If Anyone Builds It, Everyone Dies by Eliezer Yudkowsky and Nate Soares. "It" refers to Artificial Super Intelligence (ASI). A very short version of the authors' argument: You can view advanced AI as though it has its own desires and agencies, its needs will be incompatible with those of the human race, and AI has the capabilities to eliminate the humans even without the killer robots.

I have no doubt that a crafty sentient AI hellbent on destroying humanity could do so. But let's look at the first part of the argument, should we reason about AI as though it has agency and preferences? The authors make a subtle argument in their Chapter 3, that while AI doesn't have its own wants and desires, we can reason about AI as though it does. In the following chapters, the authors go all in and think of ASI as though it has preferences and acts in its own self interest.

I think of computing as a Turing machine, a device that follows a set of simple instructions, interacting with input and memory, and producing some output. The machine does not have wants or desires, all it does is follow its instructions.

But we also realize the immense complexity that can arise from such simplicity. We have Rice's Theorem that says we can't understand, in general, anything about a Turing machine's output from the code of the machine. And there's a reason why we can't prove P ≠ NP or even have a viable approach, we have no idea how to bound the complexity of efficient algorithms. But we shouldn't confuse complexity and our inability to understand the algorithm as evidence of agency and desires. Even if AI seems to exhibit goal-oriented behavior, it's a property of its training and not evidence of independent agency. 

I worry less about AI developing its own hostile agency than about how humans will wield it, whether through malicious misuse or misplaced trust. These are serious risks, but they're the kinds of risks we can work to mitigate while continuing to develop transformative technology. The "everyone dies" framing isn't just fatalistic, it's premised on treating computational systems as agents, which substitutes metaphor for mechanism.

Clyde Kruskal talks about his Father Martin on Martin's 100th birthday

Martin Kruskal was born Sept 28, 1925 and passed away on Dec 26, 2006, at the age of 81 (we did two posts for his memorial, here  and here). Today, Sept 28, 2025, is his 100th birthday. His son Clyde Kruskal wrote today's blog post as a tribute to his father.

We note that Clyde did a blog for his Uncle Bill's 100th Birthday, here, and plans on doing one for his Uncle Joe in two years. 

-----------------------------------------------------------------------------------------

My father, Martin Kruskal, was a mathematician and physicist, best known for his early work in plasma physics, the discovery (independently of George Szerekes) of Kruskal-Szerekes coordinates, the modern discovery with Norman Zabusky of solitons, and the discovery with Clifford Gardner, John Greene, and Robert Miura of the inverse scattering transform.  He had an incredible willingness to tackle interesting, seemingly small problems\(-\)some of which later turned out to be highly influential.  Here, in chronological order, is a list of some of his more esoteric and/or less well-known contributions, not necessarily research contributions (besides me).


1. Random Mappings

Renowned mathematicians Nicholas Metropolis and Stanislaw Ulam (inventors of the Monte Carlo method) posed the problem of determining the expected number of components in a random mapping from \(N\)  to \(N\). Framing this as a random graph problem: Construct a graph on \(N\) vertices by choosing, for each vertex \(i\) (from 1 to \(N\)), a random vertex \(j\) (also from \(1\) and \(N\)), and create the undirected edge \((i,j)\). If \(i=j\), no edge is created (or equivalently, a self-loop is created).  The question is: What is the expected number of connected components in such a graph?  In 1954, in his first paper after graduate school, he showed that this value is asymptotically \((1/2)(\ln(2N) + C) + o(1)\), where \(C=0.5772\ldots\) is Euler's constant. For the paper see here.

2. Computer Chess

My father was a strong chess player and, in 1956, arguably became the first person to play a game of chess against a computer.  When I learned about this in junior high school, I figured that this must be his most significant achievement.  Because the MANIAC 1 computer was slow and had little memory, the game was played on a 6×6 chessboard without bishops and simplified rules.  My father gave the computer queen odds. Spoiler alert: He won.  For more details, including the full game, see this explanation on Wikipedia here.


3. The Card Game Delphi

In 1956, Bob Abbott invented Eleusis, a card game involving inductive inference.  While the game itself was highly original, the scoring system was somewhat arbitrary.  In 1962, my father devised the game Delphi, which, according to Martin Gardner, made several important improvements, including a much more logical scoring system.  While it solved the scoring problem, Delphi turned out to be less fun to play than Eleusis.  Later, Bob Abbott created an improved version of Eleusis called New Eleusis, which, unfortunately, still did not completely solve the scoring problem.
For the rules to Delphi, see this article in Denexa Games here.

4. The Kruskal Count

My father invented a card trick, called the Kruskal Count, with the unique characteristic that the magician never touches the deck of cards during the performance.  To make this plausible, he would claim to the audience that he was psychic.  There are various YouTube videos demonstrating and discussing it.  Shortly after devising the trick, my father, brother, and I visited a young married couple.  My father performed the trick several times on the husband, who kept accusing his wife of secretly colluding with him.  She was insulted and kept denying it\(-\)truthfully. Finally my father said to the wife, Well, the cat’s out of the bag.  You have been in on it all along, and you can admit it now. (She hadn’t.) My brother and I (both teenagers) thought it was hilarious; I doubt the couple did.

The trick turned out to have serious applications: According to Wikipedia, the underlying phenomenon has applications in cryptography, code-breaking, software tamper protection, code self-synchronization, control-flow resynchronization, design of variable-length codes and variable-length instruction sets, web navigation, object alignment, and others. There are various YouTube videos demonstrating and discussing it.

The Kruskal Count was featured in an episode of NUMB3RS, which Gasarch blogged about here.

5. Surreal Numbers

My father had a lifelong fascination with infinity starting in childhood, which deepened when he read Donald Knuth’s introductory book on surreal numbers.  For more about his interaction with Knuth after reading the book, see this blog entry here.  Wikipedia provides a concise explanation on my father’s webpage about surreal numbers and his contributions.  The entry highlights important results\(-\)both positive and negative\(-\)by Ovidiu Costin, Philip Ehrlich, and the mathematical logician Harvey Friedman (see here and here for the papers).

Martin's website has the following passage, which captures the issue beautifully.

Surreal numbers, which are defined constructively, have all the basic properties and operations of the real numbers.  They include the real numbers alongside many types of infinities and infinitesimals. Kruskal contributed to the foundation of the theory, to defining surreal functions, and to analyzing their structure.  He discovered a remarkable link between surreal numbers, asymptotics, and exponential asymptotics. A major open question, raised by Conway, Kruskal, and Norton in the late 1970s, and investigated by Kruskal with great tenacity, is whether sufficiently well behaved surreal functions possess definite integrals.  This question was answered negatively in the full generality, for which Conway et al. had hoped, by Costin, Friedman, and Ehrlich in 2015.  However, the analysis of Costin et al. shows that definite integrals do exist for a sufficiently broad class of surreal functions for which Kruskal's vision of asymptotic analysis, broadly conceived, goes through.  At the time of his death, Kruskal was in the process of writing a book on surreal analysis with O. Costin.

6. Alpha-Beta Search

While in graduate school, I came across Donald Knuth and Ronald Moore's paper on alpha-beta search (see here).  They posed the question of what is the expected branching factor in a game tree with \(c\) children per node and depth \(d\), and uniformly distributed values at the leaves.  They gave a partial solution.  Gerard Baudet found a recurrence for this value and improved the bound (see here).  This was the kind of asymptotics that my father excelled at, so I asked him if he could solve the recurrence.  He solved it by finding an asymptotic value for the number of leaves evaluated.  Right after that Judea Pearl published the asymptotic value for the branching factor (see here).

At the time I figured that the original question had been answered by Pearl, so the stronger result was not interesting.  A more mature version of me might have pursued it.  In reality, answering the original question is interesting, but for a number of reasons any further improvement is not particularly interesting, so I was probably right to drop it even if for the wrong reasons.  Unfortunately it was in the file drawer lost during the move to our new building, but if anyone cares I think I remember the exact high order term.

7.  Public Key Crypto

When he learned about public key cryptography, he invented his own system based on quadratic mapping just to understand how it works.  He gave a talk on it in 1983. He showed it to Ron Rivest who said that it was not secure. Oh well.

Self-Driving Cars

A few weeks ago I took an Uber to a regional airport and was picked up by a Tesla. The driver used FSD, so-called Full Self-Driving, never touching the steering wheel during the entire trip. Should you tip a driver who just sits there? In the end I gave my usual tip and five-star rating. I figured the driver had to be there or the car wouldn't drive and he probably ponied up his own money for the FSD. I give five stars to any driver who gets me from point A to point B without major incident. Remember when five stars meant "above and beyond". Grade inflation gets us all.

But you can't tip Waymos. Last fall during a trip to San Francisco, I took my first Waymo ride. At one point a couple of people jaywalked in front of the Waymo and the Waymo promptly stopped. The car behind us started honking. Who are you honking at? It's a Waymo. It did drop me off at the wrong hotel but that's on me, who thought there would be two Hyatt Regency's in San Francisco.

In both cases the driving felt safer than the average Uber driver. It really is safer. About 40,000 people die in human-driven traffic crashes per year in the United States. But even a single accident could be devasting to a self-driving car company so they are designed to drive on the safer side. I have friends who see self-driving as the ultimate safety upgrade, especially as they lose fast reflexes as they age. 

With new technologies (to paraphrase Hemingway), things generally move gradually than suddenly. Waymo and its rivals are expanding into several cities in the US  (but not Chicago 😞) and robotaxis are all over China and across Asia. Cities like Shenzhen and Beijing have thousands of robotaxis operating daily, is the US falling behind? And why are we not seeing plans for self-driving cars in the midwest? Is it the weather, or just the usual blind spot technology companies have to this part of the country? 

Nevertheless, I suspect we'll see the vast majority of ride-share as robotaxis by the end of the decade and cars without a steering wheel soon after that. 

We can find more papers on the web than we used to. Are we reading them?

 

STUDENT: What did you do before the web to find papers?

BILL: We went to the library and copied papers to read later.

STUDENT: Did you read them later?

BILL: Well,  uh,hmm,  ...

BILL to a professor in his 80's: What did you do before copy machines?

PROF: We went to the library, took the journal off of the shelf, and read the article. We may also have taken notes on paper on the article. 

Back to 2025: I do the following sequence of events with a branch point at the end.

1) Get interested in some problem. 

I give an example:

 Rado's Theorem for equations  with a constant. Short summary:

Rado's Theorem: Let \(a_1,\ldots,a_n\) be integers. The following are equivalent

--For all finite colorings of \(N^{\ge 1}\) there is a monochromatic solution to \(\sum_{i=1}^n a_ix_i= 0\)

--Some subset of \(a_1,\ldots,a_n\) sums to 0.  

My interest: What if we look at equations which replace 0 by some other constant? AND what if you just want to look at (say) 2-colorings? 

2)  Assemble a website of papers on the topic.

I assembled a website of papers on the Rado question. I did that. The website is   here. 

3)  I then read the papers and understand them. Or not. 

I intend to do the following: 

a) Read the paper with pen and pad and take notes, draw diagrams, do examples. I may create some  handwritten notes. The benefit of the notes is from making them. The actual notes are terrible. 

b) Type in the notes and while doing that polish them. I might work with a student on this.

c) If needed make slides out of the proof for presentation.

I sometimes go straight from the paper to the slides. I've stopped doing that since it is valuable to first go through the Understanding the proof  phase before going to the Best way to present the proof phase.

----------------------------------------

Step 3 can be a problem. I have many website of papers that I never got around to reading. The key for me is to strike while the iron is hot that is, SOON after assembling the papers READ them.

 For Rado's Theorem with constants I have not gotten around to reading any of the papers yet. 

There is some benefit to having to read a paper in the library since then you actually read it. I am NOT saying  things were better when I was a kid. The lesson is more of how to combine current technology with the helpful constraints of a prior era. 

Another approach: go to the library and look through journals to find something interesting. I've done this a few times with success. I blogged about one of them  here

What is "PhD-Level Intelligence"?

When announcing Open-AI's latest release last month, Sam Altman said "GPT-5 is the first time that it really feels like talking to an expert in any topic, like a PhD-level expert." Before we discuss whether GPT-5 got there, what does "PhD-Level intelligence" even mean?

We could just dismiss the idea but I'd rather try to formulate a reasonable definition, which I would expect from a good PhD student. It's not about knowing stuff, which we can always look up, but the ability to talk and engage about current research. Here is my suggestion.

The ability to understand a (well-presented) research paper or talk in the field.

The word "field" has narrowed over time as knowledge has become more specialized, but since the claim is that GPT-5 is an expert over all fields, that doesn't matter. The word "understand" causes more problems, it is hard to define for humans let alone machines.

In many PhD programs, there's an oral exam where we have previously given the candidate a list of research papers and they are expected to answer questions about these papers. If we claim a LLM has "PhD-level" knowledge, I'd expect the LLM to pass this test.

Does GPT-5 get there? I did an experiment with two recent papers, one showing Dijkstra's algorithm was optimal and another showing Dijkstra is not optimal. I used the GPT 5 Thinking model and GPT 5 Pro on the last question about new directions. A little more technical answers than I would have liked but it would likely have passed the oral exam. A good PhD student may work harder to get a more intuitive idea of the paper in order to understand it, and later on extend it.

You could ask for far more--getting a PhD requires significant original research, and LLMs for the most part haven't gotten there (yet). I've not had luck getting any large-language model to make real progress on open questions and haven't seen many successful examples from other people trying to do the same. 

So while large-language models might have PhD-level expertise they can't replace PhD students who actually do the research.

``I'm on vacation so I won't be checking email'' will sound funny soon. Maybe it already does.

 "I'll be on vacation so I won't be checking email.''

"I can't be at the meeting since I will be out of town''

Technology has made it so that:

a) You really CAN get email when you are on vacation.

b) You really CAN go to a meeting if you are out of town (if the meeting is on Zoom which is becoming more and more common).  (My proofreader tells me that Zoom is spelled with a capital Z.  I did not know that! The phrase I  Googled is formally correct, though I googled is acceptable. I have never seen anyone say or write I Binged  or I binged  for searching, though I have seen I binged watched Babylon Five  for example.  I have never seen  I Yahooed or I yahooed  for search or for any other reason. Fun fact: the term Yahoo was coined by Jonathan Swift for use in the book Gulliver's Travels.) 

Caveats:

1) You are on vacation! You DO NOT WANT to answer email!

2) You are out of town at a conference and the meeting is at the same time as a talk you want to go to.

3) There are too many meetings so it's good to have an excuse to not go to some. 

Personal:

This is one issue where I may be LESS of a Luddite than Lance:

When Lance is on vacation, he DOES NOT get email.

When I am out of town, I DO get email, and respond to it. This first struck me when I was on a riverboat cruise in France and I got an email from my chairman asking if I would be on some committee (I said yes).  I was more `in contact' than people on campus who don't respond to email. 

How we talk about things: My advisor told me he would be giving a talk in Zurich. I azoomed he meant a talk on Zoom. He actually meant in person. Fortunately it was recorded so I didn't have to get up at 5:00 a.m.  to see it. (My spellcheck thinks azoomed is not a word. It is correct. For now.)