Computational Complexity

The National Science Foundation was founded on May 10, 1950, 75 years ago last Saturday. No doubt the NSF has seen better days, but first let's take a look back.

At the end of World War II, Vannevar Bush, Director of the Office of Scientific Development, wrote Science, The Endless Frontier, where he laid out the importance of scientific research and the need for the US government to foster that research. 

A new agency should be established, therefore, by the Congress for the purpose. Such an agency, moreover, should be an independent agency devoted to the support of scientific research and advanced scientific education alone. Industry learned many years ago that basic research cannot often be fruitfully conducted as an adjunct to or a subdivision of an operating agency or department. Operating agencies have immediate operating goals and are under constant pressure to produce in a tangible way, for that is the test of their value. None of these conditions is favorable to basic research. Research is the exploration of the unknown and is necessarily speculative. It is inhibited by conventional approaches, traditions, and standards. It cannot be satisfactorily conducted in an atmosphere where it is gauged and tested by operating or production standards. Basic scientific research should not, therefore, be placed under an operating agency whose paramount concern is anything other than research. Research will always suffer when put in competition with operations.

The report laid out the National Research Foundation that would actually spread across three agencies, DARPA, NIH, and the NSF.

While Bush didn't significantly mention computing, given the time, Computing would become a central part of NSF's mission with the establishment of the Computing and Information Science and Engineering (CISE) directorate in 1986, placing Computing at the same level as the Math and Physical Sciences Directorate and the Engineering Directorate.

In 1999, the President’s Information Technology Advisory Committee (PITAC) issued a report that led to the NSF Information Technology Research (ITR) program, which became one of the largest NSF research initiatives of the early 2000s. The report helped reframe computing not just as infrastructure but as a scientific discipline in its own right, deserving of the same kind of basic science funding as physics or biology.

CISE has led many initiatives through the years, for example the TRIPODS program established several centers devoted to the theoretical study of data science.

In recent weeks, the NSF director stepped down, hundreds of grants were canceled, new grants were put indefinitely on hold, indirect costs on new grants will be capped at 15%, and many staff members were pushed out. Divisions below the directorates are slated for elimination, advisory committees have been disbanded, and Trump's proposed budget cuts NSF’s allocation by about half. The CISE AD (Assistant to the NSF Director, or head of CISE), Greg Hager, stepped down last week and through the CRA sent a message to the community.

Under these circumstances, my ability to carry out my vision, to provide a voice for computing research, and to provide authentic leadership to the community are diminished to the point that I can have more impact outside NSF than within it. Echoing Dr. Nelson’s powerful article, leaving “allows me to speak more clearly in my own language,” and, in doing so, even more effectively amplify the work of the incredible, dedicated CISE leadership and staff who continue to strive to fulfill NSF’s mission. 

As I move beyond NSF, I will continue to make the case for computing research. Computing is central to so much in today’s world and computing advances are now core assets to the Nation’s research enterprise. NSF’s support for the past 75 years has forcefully demonstrated the value of computing research for advancing national health, prosperity and welfare; enhancing national economic competitiveness; securing the national defense and helping promote all of science and engineering. NSF-funded work has continually catalyzed new innovations, created new industries, and made us the envy of the world.  

We all need to join Greg in continuing the fight to ensure that Vannevar Bush's vision continues to survive another 75 years and beyond.

 The New Pope is Pope Leo XIV (pre-Pope name is Robert  Prevost). 

1) Pope names are one of the few places we still use Roman Numerals. I saw an article that was probably satirical that Americans prefer Roman Numerals (the numbers Jesus used) over Arabic Numerals. Also note that Pope Francis did not have a Roman Numeral- that is because he is the first Pope Francis. They could call him Pope Francis I now, rather than later, to avoid having to rewrite things. (John Paul I took the name John Paul I.)

2) Over the years I have  read the following and had the following thoughts (Spoiler- I was wrong on all of them)

a) The last non-Italian Pope was Pope Adrian VI who was Pope from Jan 9 1522 to Sept 14 1523. His Wikipedia entry: here. He was 80 years old when he became Pope and died of  a heart attack.

BILL THOUGHT: We will never see a non-Italian Pope again.

REALITY: John Paul II from Poland was Pope from 1978 until 2005. His Wikipedia page is here

MORE REALITY: Since then we've had Pope Benedict XVI (Germany), Pope Francis I (Argentina),and Pope Leo  XIV (America). I now wonder if we will ever have an Italian Pope again but I make no predictions. 

b) There will never be an American Pope because people think that America already has too much power and if there ever was an American Pope then people would think it was engineered by the CIA.

BILL THOUGHT: That sounded correct to me. Not that the election would be engineered by the CIA, but that people would think that. 

REALITY: Pope Leo XIV is American. Some MAGA people are calling Pope Leo a Woke Marxist Pope (see here). Not the type the CIA would install. 

QUESTION: How much power does the Pope really have? I ask non-rhetorically as always. 

c) The shortest Pope Reign was Pope Urban VII (1590) who reigned for 13 days. The tenth shortest was Pope Benedict V (964) who reigned for 33 days. I originally thought the short reigns were from assassinations, but I looked it up and there were two that may have been murdered, but the rest died of natural causes. Having looked it up I wrote it up here.

BILL THOUGHT: The 10th shortest reign was 33 days. With better health care and less skullduggery in the Papacy that won't happen again.

REALITY: Pope John-Paul I in 1978 died of a heart attack after being Pope for 33 days. 

d) The last Pope to resign was Pope Gregory XII in 1415 (his Wikipedia page is here). He resigned to heal a  schism in the church (its more complicated than that, see his Wikipedia page).

BILL THOUGHT: We will never see a Pope resign again.

REALITY: Pope Benedict XVI resigned (see here for the Wikipedia page on the resignation) in 2013. He said it was for health reasons.

BILL THOUGHT: Now that Pope Benedict has resigned it will be easier for later popes who feel they are not healthy enough for the job to resign. But I make no predictions. 

3) Pope Leo XIV has a degree in Mathematics. I emailed the following to my Ramsey Theory class which is an excerpt from his Wikipedia Page with one incorrect sentence. See if you can spot it. I will tell you what it is, and what the real line is, later. 

Prevost earned a Bachelor of Science (BS) degree in mathematics from Villanova University, an Augustinian college, in 1977. His Undergraduate Thesis was on Rado's Theorem for Nonlinear Equations.  He obtained a Master of Divinity (MDiv) from Catholic Theological Union in Chicago in 1982, also serving as a physics and math teacher at St. Rita of Cascia High School in Chicago during his studies. He earned a Licentiate of Canon Law in 1984, followed by a Doctor of Canon Law degree in 1987 from the Pontifical University of Saint Thomas Aquinas in Rome. His doctoral thesis was titled The Role of the Local Prior in the Order of Saint Augustine. Villanova University awarded him an honorary Doctor of Humanities degree in 2014

4) He is not the first Pope who knew some mathematics. In a general sense people used to be more well-rounded before fields got so specialized. So in that sense I am sure that some prior Popes knew some math. But more concretely Pope Sylvester II was, according to the article When the Pope was a Mathematician Europe's leading mathematician, (at the time a modest distinction) reigning as Pope Sylvester from  997 to1003. His Wikipedia page is here.

5) Since Pope Leo XIV was a mathematician, as Pope he won't only know about sin but also about cos.

6) The name Leo struck me since one of my TAs is named Leo. I asked him, if he became Pope, would he change his name. He said 

Hmm, after careful consideration, I think I would take another name. I like being Leo, but I think I would want to try out a different name. I looked up Papal names, and I would probably pick something cool like Boniface, Honorius, or Valentine. But I would do the name change after the semester ends so as not to screw up the payroll office. 

7) Popes did not always change their names. For a long article on that see here. For a short version here are some points:

a) The first Pope to change his name was born Mercurious, a Pagan God Name, and changed it to be Pope John II. That was in 533. 

b) The name-change did not become standard for a while. Before the year 1000 only 3 Popes changed their names, all to John. The other two had given name Peter and felt they should not take the name Peter since Peter was the first Pope and an apostle. Kind of like having a jersey number retired by a sports team.

c) After the year 1000 some changed,some didn't, but the last one to not change was Pope Marcellus II in 1555. His reign was 22 days, though I doubt that is related to not changing his name. 

8) Math question: What is the average length of a Papacy and what is the average length of a presidency (of America)?

The first Pope was Peter, began in 30AD.

The 266th Pope was Francis whose reign ended in 2025.

SO we have 266 Popes in 1995 years, so the average reign is 7.5 years.

The first president was George Washington whose presidency began in 1789.

The 46th president was Joe Biden and it ended in 2025.

SO we have 46 presidents (we ignore the Grover C thing) in 236 years, so the avg reign is 5.1 years.

The 7.5 and 5.1 are more different than they look since the length of presidents is usually 4 or 8 years,while the length of a Papal reign has had a min  of 13 days and a max of 31 years (Pope Pius IX).

I'l be curious what the standard deviation and deviance are for both Papal Reigns and Presidents. I suspect that it's much bigger for Papal reigns, and not just because the presidency is at most 8 years (with one exception-FDR was president for 12 years). 

9) There was betting and betting markets on the next Pope. This raises the question of how often someone NOT on the short list (so probably not bet on much) becomes Pope. Lets look at the last few:

Pope Leo XIV- not on the short list

Pope Francis- not on the short list

Pope Benedict XVI- a favorite

Pope John Paul II- not on the short list

Pope John Paul I- I don't know and I will stop here.

Upshot: it may be foolish to bet on the next Pope. Even more so than betting on the Vice Prez nominee which I commented on here.

10) Art imitates life: Some of the cardinals at the conclave watched the movie Conclave to get an idea of what a conclave is like. I suspect the real conclave was much less dramatic than the movie Conclave. 

13) The Wikipedia entry for Pope Leo XIV does not say his undergraduate thesis was on 

Rado's Theorem for Nonlinear Equations. 

It was on 

The Canonical Polynomial Hales-Jewett Theorem.

(One of the commenters believed this which I thought was clearly a joke (perhaps I am wrong) so I now STATE that I am only kidding to avoid any more disinformation.) 

I reviewed a paper recently and I had to agree not to use AI in any aspect of the reviewing process. So I didn't but it felt strange, like I wouldn't be able to use a calculator to check calculations in a paper. Large language models aren't perfect but they've gotten very good and while we shouldn't trust them to find issues in a paper, they are certainly worth listening to. What we shouldn't do is have AI just write the review with little or no human oversight, and the journal wanted me to check the box probably to ensure I wouldn't just do that, though I'm sure some do and check the box anyway.

I've been playing with OpenAI's o3 model and color me impressed especially when it comes to complexity. It solves all my old homework problems and cuts through purported P v NP proofs like butter. I've tried it on some of my favorite open problems where it doesn't make new progress but it doesn't create fake proofs and does a good job giving the state of the art, some of which I didn't even know about beforehand.

We now have AI at the level of new graduate students. We should treat them as such. Sometimes we give grad students papers to review for conferences but we need to look over what they say afterwards, the same way we should treat these new AI systems. Just because o3 can't find a bug doesn't mean there isn't one. The analogy isn't perfect, we give students papers to review so they can learn the state of the art and become better critical thinkers, in addition to getting help in our reviews. 

We do have a privacy issue. Most papers under review are not for public consumption and if uploaded into a large-language model they could become training data and be revealed if someone asks a relevant question. Ideally we should use a system that doesn't train on our inputs if we use AI for reviewing but both the probability of leakage and amount of damage is low, so I wouldn't worry too much about it.

If you are an author, have AI review your paper before you submit it. Make sure you ask AI to give you a critical review and make suggestions. Maybe in the future we'd required all submitted papers to be AI-certified. It would make the conference reviewers jobs less onerous.

For now, humans alone or AI alone is just not the best way to do conference reviews. For now when you do a review, working with an AI system as an assistant will lead to a stronger review. I suspect in the future, perhaps not that far, AI alone might do a better job. We're not there yet, but we're further than you'd probably expect.

In a recent post by Scott (see here or just read my post which includes his post) he listed topis that he conjectured would NOT cause an outrage.

I was going to write a long comment in his comments section,  which would only be read by people who got to comment 100 or so. OR I could comment on it in my blog.

SO, here is his blog post and my comments on it.

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

A friend and I were discussing whether there’s anything I could possibly say, on this blog, in 2025, that wouldn’t provoke an outraged reaction from my commenters.  So I started jotting down ideas. Let’s see how I did.

1) Pancakes are a delicious breakfast, especially with blueberries and maple syrup.

BILL: Pancakes have a terrible ratio of health to enjoyment.

2) Since it’s now Passover, and no pancakes for me this week, let me add: I think matzoh has been somewhat unfairly maligned. Of course it tastes like cardboard if you eat it plain, but it’s pretty tasty with butter, fruit preserves, tuna salad, egg salad, or chopped liver.

BILL: UNFAIRLY MALIGNED. That's an interesting concept in itself since there are so many opinions on the internet there is not really a consensus on.... anything.  My 2 cents: I like the taste of cardboard and hence I like the taste of matzoh.

3) Central Texas is actually really nice in the springtime, with lush foliage and good weather for being outside.

BILL: I WILL DEFER to Scott, who is now a Texan, on this one.

4) Kittens are cute. So are puppies, although I’d go for kittens given the choice.

BILL: PETS are a waste of time and energy. My opinion shows something more important: Scott and I disagree on this but we are not OUTRAGED at each other.

5) Hamilton is a great musical—so much so that it’s become hard to think about the American Founding except as Lin-Manuel Miranda reimagined it, with rap battles in Washington’s cabinet and so forth. I’m glad I got to take my kids to see it last week, when it was in Austin (I hadn’t seen it since its pre-Broadway previews a decade ago). Two-hundred fifty years on, I hope America remembers its founding promise, and that Hamilton doesn’t turn out to be America’s eulogy.

BILL: Agree. Also lead to the best math novelty song of all time, See here.

6) The Simpsons and Futurama are hilarious.

BILL: The cliche The Simpsons was better in its first X seasons is true, but it can still crank out an excellent episode once in a while. The episode  Treehouse of Horrors: Simpsons Wicked This Way Comes  (from 2024--Wikipedia entry here)  is a microcosm of the series: Two okay satires of two okay stories by Ray Bradbury and then a BRILLIANT satire of Fahrenheit 451. (Spell check thinks Treehouse is not a word .I looked it up to see what the geat God Google would say.  The Treehouse of Horror episodes of the Simpsons use Treehouse. I googled Is Treehouse One word and got a YES. This is a rare time when spellcheck is just wrong.)

BILL: I think Futurama benefited from being on the air, then off, then on, then off, then on (is it on now?) since it came back with new stories.