Lance Fortnow's Blog

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

(After I wrote this post Lance tweeted a pointer to a great talk by Ronald de Wolf with more examples, and also examples of quantum proofs, see here.)

I was teaching the prob method for lower bounds on Ramsey Numbers (see my slides here).

As often happens, a student said:

That's not a new technique--- you're just counting.

My response

1) For this example, it can be rephrased as counting, but there is no advantage in that. 

2) There are other examples where either 

a) You could rephrase it as counting but it's MUCH EASIER to use probability, or

b) You really CANNOT rephrase as counting.

And I came prepared-I presented the following result (see my slides here):

Theorem: Let \(G\) be a graph on \(n\) vertices where every vertex has degree \( \ge d \). Then \(G\) has a dominating set of size 

\( \le n \frac{\ln(d+1)+1}{d+1} \). 

The proof uses that \( E(X+Y)=E(X)+E(Y) \). I cannot see a way to make the argument into a counting argument. Clearly 2a is true. It may even be that 2b is true, though that would be hard to formalize.

The student admitted that yes, the Dom Set Theorem either could not be rephrased as a counting argument or it would be hard to do so. 

Can you make it into a counting argument? Would you want to bother? 

When I first became a professor I had it all planned out, I would do research, teach and supervise students, get tenure and do more research, teach more courses, and supervise more students for the rest of my life. But once I got tenure, instead of feeling very excited, I felt kind of depressed. I achieved the main goal I put out for myself. Would I really just do the same stuff for the rest of my career?
I even went to a career counselor who gave me a personality test. I'm a classic INTJ, a perfect fit for a scientific researcher. But I just couldn't keep doing the same and tried to mix it up in different ways. I had children, did a sabbatical in Amsterdam, changed jobs multiple times. A colleague called me "a restless soul."
I took service roles in the field, started this blog, wrote survey articles and a popular science book. In my research for a while I kept doing complexity though trying to focus on applying it to other disciplines such as economics. But I found myself often working on problems that few others cared about.
Eventually I became a department chair and a dean, during an incredible transformation in computing as we moved towards the data-driven future we now inhabit. Now that I've returned to the professoriate I lack the excitement and probably the skills to go back to complexity, which has become more of a mathematical field mostly ignoring the changes we've seen in computing.
In an interview for an administrative job I did not get, I gave a vision talk emphasizing growth and impact. Afterwards when I met with the faculty in small groups, one of them, a CS theorist whom I’ve known for decades, looks at me and says “You’ve changed". Yes. And they hadn't. Two responses to the same restlessness, perhaps. Or maybe they were never restless at all.

Coding Style Is Important

Does coding style matter? We teach students how to write code and about algorithms. But, do we discuss coding style? Some people may say that style is just personal preference. But, there is undoubtedly good style and bad style, both for prose and for code. Following is a guest post by David Marcus that is a book review of a book that focuses on coding style.

====

This is a review of the book "Professional Pascal: Essays on the Practice of Programming" by Henry Ledgard. This book changed my life: After reading it, I rewrote all my code.

"Professional Pascal" is not about algorithms. It is about writing code. I consider it to be the Strunk & White for programmers.

While programs must be understood by the computer, they must also be understood by people: We need to read the code to determine that the program is correct (testing can only show that it is incorrect, not that it is correct). We need to read the code to maintain/improve/extend/debug/fix it. This applies even if you are the only person who will ever read or use your code. You probably spend more time reading your code than writing it. If you need to do something with code that you wrote long ago, you will be grateful if the style makes it easy to understand.

If you don't use Pascal (or Delphi), don't be put off by the "Pascal" in the title. Almost all of the advice can be applied to any programming language.

I won't try to summarize what Professor Ledgard has written in his book: He explains it much better than I can. But, I will mention a few of the topics that he covers and some things that I found notable.

One of the essays in the book is "The Naming Thicket". Names are important. Variables should be nouns, procedures should be verbs, booleans should be adjectives.

I was once reading some code in a commercial product, and I saw several methods that had a variable named "Ary". I eventually figured out that this was an abbreviation for "Array". Of course, this was a terrible name: "Array" didn't tell me what the contents of the array was, plus the unnecessary abbreviation turned it into a puzzle.

Another time I was reading a method in a commercial product and the method had a two-letter name. It wasn't clear to me what the two letters meant. I eventually guessed that they were the initials of the developer. I confirmed this with another developer who worked on the same team.

Another essay in the book is "Comments: The Reader's Bridge".

Following Professor Ledgard's advice, in my code I put a comment at the beginning of every procedure, function, method, unit, group of constants/types, and every class, but I never put comments mixed in with the code. If I'm tempted to put a comment in the code, I just make it a method name and call the method at that point in the code.

I own a commercial database library that comes with source code. There are some comments in the source, but most of them appear to be there so that they can be extracted into the Help. I know someone who works for the company. I asked them whether the source code that they ship is the same as their internal copy. I thought maybe they strip out some of the comments in the shipped version. Nope. It is the same as their internal version.

Another essay in the book is "Program Layout". To differ slightly from Professor Ledgard, I would say the layout should make the syntax clear (not the semantics). In case you haven't figured it out, the correct indentation for blocks is three spaces (I don't think Professor Ledgard says this, but he indents three spaces in his examples).

Another essay in the book is "A Purist's View of Structured Programming". Only use one-in, one-out control structures. Never exit a method or block in the middle. If you know the code is written to adhere to this rule, it is much easier to understand: You don't have to scan the whole method looking for quit/exit/return statements.

Another essay in the book is "The Persistence of Global Variables". I once had a bug in one of my programs. I spent a lot of time trying to figure out what was wrong. The problem was in a method that called several other methods of the same class, something like

   DoThis( X, Y );
   DoThat( X, Y );

After much confusion, a light bulb went off in my head when I remembered that DoThis was changing the value of the object's fields. The object is global to the method calls because the compiler passes it in, but it isn't explicitly listed in the parameters/arguments of the methods. After that experience, I always include the object when calling a method, e.g.,

   self.DoThis( X, Y );
   self.DoThat( X, Y );

Another essay in the book is "It Worked Right the Third Time". When I write code, I compile it to catch syntax errors (like a spell checker). I then proofread it to make sure that it is correct (just like reading a math proof to check it). (Ideally, I will print the code out, but if the changes are scattered in multiple files, then viewing a diff onscreen works better.) Only then will I try it. The emphasis should be on writing good code. No amount of testing can make poor code good.

This book was published in 1986, and that is when I first read it. So, why am I writing a book review now? I read a lot of code written by people who make their living writing code. And, all of these people would benefit from reading this book.

Professor Ledgard has also written the books "Software Engineering Concepts (Professional Software, Vol 1)" and "Programming Practice (Professional Software, Vol 2)" (both written with John Tauer) . Much of the material in "Professional Pascal" is also in these books. "Professional Pascal" is shorter, so if you are only going to read one of these books, read it. If a book is too long, here is an article: "Coding Guidelines: Finding the Art in the Science: What separates good code from great code?" by Robert Green and Henry Ledgard, ACM Queue, vol. 9, No. 11, 2011-11-02. The link is here

 

 

This will be one of a series of posts that I've always wanted to write but I needed to wait until I was no longer an academic administrator.
Logic is critical to proving theorems but it's the wrong way to argue for resources.
When I was such an administrator, faculty would come and argue, generally for more salary, more office space, more hiring in their specialty or less teaching. Since I had many mathematicians and computer scientists, I'd often get these logical arguments. These arguments were typically fitted to generate the conclusion. How? By choosing the right assumptions, or putting in certain facts, or a certain interpretation of the facts. I've never seen a faculty member give a logical argument on why they should be paid less.
I could point out the faulty assumptions or sometime faculty logic but you can never convince someone they are wrong, especially if it means they won't get what they want. So I generally just agree with them, try to to help out if I can but generally say limited resources tie my hands, which usually is true. 
What's the right way to argue? Show why helping you would strengthen the department/college/university, how you don't need that many resources and how you can generate more resources (say through grants). Arguing to grow the pie always wins over arguing for a bigger slice. I was also more receptive for requests that helped students rather than the faculty themselves.

(This post was inspired by  George Foreman, who passed away March 21, 2025, at the age of 76.)

About 10 years ago I asked my class

What is the best invention or tech advance of the last 50 years?

Here are the answers I got NOT ranked.

1) The internet. We can look things up so easily! (see my post on one aspect of this here). Young people reading this blog have no idea what the world was like before the internet. Here is a short story that shows how much has changed.

At MIT in 1982 I saw Anil Nerode give a great talk about Recursive Mathematics: using recursion theory to show that some theorems whose proofs were not effective could not be made effective (e.g., there is a computable 2-coloring of pairs of naturals with no decidable infinite homogeneous set, so the proof of Ramsey theory on \(K_N\) has to be non-effective). The talk got me interested in the topic, so that day I went to the math library (ask your grandparents what a library is) and found the paper journals that had some of the articles he talked about (Journals used to be on paper? See my post  about that.) I then copied the articles on the copy machine (ask your grandparents what a copy machine is) and read them. A few years later Anil Nerode asked me to write a survey of recursive combinatorics for a collection of articles in recursive mathematics. He was one of the editors of a joint America/USSR project (ask your parents what the USSR was) which I was happy to do. The book was delayed when the USSR fell apart (ask your parents about that important historical era), but was eventually published. The survey is 131 pages and is here. The book, Handbook of Recursive Mathematics, is in two volumes. Its available on Amazon Volume 1 and Volume 2. I've also sometimes seen it available for free download though I don't know if it really is or if thats some kind of scam (if your grandparents try to download it warn them that it might be a scam).

2) Advances in medicine. You can have an operation and be home that night (this is partially medical advances and partially the insurance companies forcing you to have short stays). I asked the question pre-COVID. If I asked it again, I may have some people saying vaccines. 

3) VCR/DVD/DVR/Streaming so we have a lot more control over our entertainment (Is this really on a par with medical advances? Yes- you can watch TV of your choice while you recover.)

4) Easy Pass for Toll Booths. The students said that it was always a pain having to bring change to toss into a basket at the toll booth. And sometimes they missed. 

5) The George Foreman Lean Mean Fat-Reducing Grilling Machine. The student really liked using it and said that burgers were tastier and healthier. I asked him if he really thought George Foreman got to be the heavyweight champion of the world (twice!) because of the grill. He didn't know George Foreman had been a boxer, he thought that George Foreman was a pitchman.  Which is true but inomplete. Whether he is a pitchman or a boxer or an ex-boxer, does he really know about enough about  healthy eating so that you should  take his advice? Note also that he has a financial incentive to  belief that the grill  produces tasty and health food.  See here for a blog post on the illogic of advertising. 

6) The Cell phone. It would be rude to, at a party, go into a corner and read a newspaper. But it is socially acceptable to go into a corner and read the news (or anything else) on your phone. I discussed this, though about laptops, as part of a post here. On the one hand, maybe it was good to be forced to talk to people. On the other hand, I can check my mail without being at home or the office!

7) THE CELL PHONE!!!!!! See Lance's post here.

8) Caller ID. The Cell Phone makes it possible to call anyone, anytime. Caller ID makes it possible to avoid talking to anyone, anytime. Symmetry!

9) ChatGPT was not on the list 10 years ago but might be now. And other AI things will be also.

But for now I ask: What do YOU think were the greatest tech advances of the last 50 years? If you prefer thinking on a full stomach then grill some burgers and eat them before answering. 

BILL to LANCE: Anything you want to add?

LANCE:

9) GPS - First launched in 1978 and now you never get lost, even at sea.

BILL: Some people trust their GPS to much, see here, though I think these stories happen less and less over time. 

10) CNN - Watching wars play out in real time was a game changer.

 BILL comment on CNN: In 1991 I was on a cruise. In the time I was gone their was an attempted cue against Gorbachev. I didn't hear anything about it until the cruise was over. CNN existed but it was not-a-thing to have it wherever you go. The next time I went on a cruise was 2022. While on that cruise, Gorbochev died and I heard about it right away. Two points here:(a) How fast we got news anytime-anywhere has changed a lot, and (b) For the sake of the Gorbachev family I should stop going on cruises. 

11) Cloud Computing - Enabled small startups to do big things.

BILL Sometimes very small, like one person. New word: Solopreneur

I've heard this story from a few places. A father watches Back to the Future II with his kid. The 1989 movie view of 2015 looks entirely different when in fact not much has changed except for the fashion and the lack of mobile phones. This is supposed to be a parable about the lack of technological progress.

I disagree. It's about a lack of imagination of the future because of those phones. Phones that are hidden from sight, and have become so ubiquitous we take them for granted.

The phone in your pocket is more powerful than the most powerful computer of 1985 and it's not even close. But that's the least interesting thing about the phone.

You no longer need a printed newspaper, encyclopedia, atlas, almanac, dictionary, thesaurus, dining guides, programming manual or any other reference book. The printed sports almanac at the center of the plot of the movie doesn't exist anymore. 

You can read virtually any book ever published, listen to any song ever recorded, watch any movie ever filmed. You have access to nearly all publicly available information. You can watch major sporting events live. On that phone.

You can buy tickets to any event and save and use them on your phone. You can pay for just about anything with your phone, and if you wish ship it anywhere.

You no longer have to fold a map or ask for directions. The phone will give you directions, taking account traffic and transit delays, and guide you along the way.

When visiting a foreign country you can point your phone at a sign in Japanese and have the words magically replaced by English. Take a picture of a menu in German and have it describe the dishes in English. Instantly translate voice as well.

You can have a conversation with your phone about anything. It will understand your voice and respond likewise. 

You can take photos and videos on your phone and share them instantly with your friends or with everyone around the world. The quality is far superior to any consumer-level camera from 1985. Or you can have the phone create its own photos and videos based on your descriptions. 

It's also, of course, a phone. You can speak to anyone anywhere, with video if desired, for zero marginal cost. Back in 1985 it cost about a dollar a minute to call someone in a different state, and much more internationally, on a landline. You can have impromptu video meetings and you can send messages to anyone and share them with everyone. 

And I'm just scratching the surface. 

So between the phone and the flying hoverboards, I'll take the phone any day.

Tom Lehrer passed away on July 26, 2025, at the age of 97. I wrote a blog-obit here. One of my readers read the post and went down a rabbit hole (or did he?), which lead to a blog post about rabbit holes here. 

A few more notes about Tom L.

1) When someone of interest to our readers dies, Lance calls me (he seems to always know before I do) to discuss who should do the obit (me, him, someone else, or perhaps no obit needed). This was a case where there was no need for a discussion.  To say I am a fan of novelty songs would be an understatement---I've been a fan of novelty songs before I was a fan of mathematics. A link to my website of novelty songs by topic, including Math, is here

2) Whenever Lance calls I answer with Who Died? 

3) Who was the oldest novelty song singer to die in the Summer of 2025? The summer is not over yet but I think the answer is known. And it's NOT Tom L!

Jane Morgan, a singer, died on August 4, 2025, at the age of 101.  She recorded a parody of  Johnny Cash's A Boy Named Sue titled A Girl Named Johnny Cash 

A boy named sue:  here

A girl named Johnny Cash: here

Wikipedia Page for Jane Morgan: here

To my knowledge, Jane Morgan only had that one novelty song so calling her a novelty singer is a stretch, but its a great song, so I will call her a novelty singer.  (I checked if the flipside of that song was a novely song. It was Charley, a love song, not a novelty song. Ask your grandparents what a flipside is.) 

4) Tom Lehrer and Jim Lehrer (news anchor on PBS, deceased) are not related.

I googled how many people have last name Lehrer

Google-AI:  FamilySearch.org estimates there are 211,503 records for the surname.

But  says approximately 5982 bear this surname.

I'm surprised by the large gap there.

5) There have been more elements found since Tom L did The Elements. I wondered whether someone updated it. Of course they did:

The Original by Tom L: here

Updated version by Leonard  Lehrman that has the latest element, Number 118, Oganesson: here

I've heard that 118 is natural barrier- we probably won't create 119 or higher. Elements that high are created, not discovered. They also don't last long. 

6) There are many elements, so a list-song made sense. There are a lot of complexity classes, so a list-song makes sense for those as well. 

Dave Barrington sings Song of the Complexity Classes: here

7) How many people emailed me to tell me that Tom L passed away? R(5).

8) One of my favorite and less known Tom L songs whose advice he did not take: Selling Out

9) Tom L wrote a paper with R.E. Fagen (Not Ronald Fagin) for the NSA. It's a real math paper, but note the third reference in the bibliography, the paper is here.

Last month the New York Times highlighted some AI generated short movies, including Total Pixel Space, by Jacob Adler that gets philosophical about information, à la infinite monkeys. It imagines the finite number of images and video that contain all human history, both real and fake, along with all possible creatures, and even the rise and fall of alien civilizations.

Let's talk about the math. According to the video there are roughly 7.8 x 107,575,667 possible 1024x1024 images, and 9.3 x 101,309,075,411,322 possible two hour films, incomprehensibly large numbers. The narrator acknowledges that most of the images are random noise.

But within this ocean of pixel possibility, natural images are but a drop. Recognizable scenes, faces and objects are extremely rare islands in a vast sea of noise.

So how do we capture which images actually matter? Let's visit our friend Kolmogorov Complexity, which measures information by the amount we can compress. A JPEG image typically compresses (lossily) to about 200 KB, which reduces the number of images to 8.7 x 101,061,650. Still enormous.

All the images and videos were generated by short prompts. JPEG compression reduces raw pixel space by discarding details our eyes don’t notice. Prompts do something similar at a higher level: they compress ideas, not pixels.

Consider prompts of length 100 over a 10,000 word alphabet typically used in prompting and we're down to 10400 possibilities, a mere quintic of the number of atoms in the universe. And you could cut that down by considering grammatical structure.

Now from a prompt you won't get the same image each time, based on the randomness of machine learning. But that's the whole power of AI, the randomness just gives us examples of the structure embedded in the prompt. It's the structure that matters.

And perhaps those monkeys would be more efficient if they entered prompts into AI, instead of generating random text. What images they could produce!