Sunday, September 21, 2025

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

Wednesday, September 17, 2025

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.

Monday, September 15, 2025

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

Thursday, September 11, 2025

Is the Prob Method `Just Counting'- I say no and HELL NO

(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? 

Monday, September 08, 2025

A Restless Soul

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.

Tuesday, September 02, 2025

Guest Post on Why Coding Style is Important

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