Rules vs Standards

You can write laws that are very specific, like the US tax code, or open to interpretation like the first amendment. In the literature these are known as rules and standards respectively. 

In computational complexity, we generally think of complexity as bad. We want to solve problems quickly and simply. Sometimes complexity is good, if you want to hide information, generate randomness or need some friction. But mostly we want simplicity. How does simplicity guide us in setting guidance, either through rules or standards?

 

Rules are like a computer program. Feed in the input and get an output. Predictable and easy to compute. So why not always have tight rules?

Nobody ever gets a computer program right the first time, and the same goes for rules. Rules can be overly restrictive or have loopholes, leading to feelings of unfairness. Rules can require hoops to jump through to get things done. Rules don't engender trust to the ones the rules apply to, like very tight requirements on how grant funds can be spent. We know that in general we can't predict anything about how a computer program behaves, so why do we trust the rules? 

A good example of a standard is that a PhD dissertation requires significant original research. Rules are things like the exact formatting requirements of a thesis, or statements like a CS thesis must contain three papers published in a specific given set of conferences. 

As an administrator I like to focus on making decisions based on what's best for my unit, as opposed to ensuring I followed every letter of every rule. Because if you live by the rules, you'll die by the rules.  People will try to use their interpretation of the rules to force your hand.

Sometimes we do need strict rules, like safety standards, especially for people unfamiliar with the equipment. Structured rules do give a complete clarity of when an action is allowed. But it also gives an excuse. Have you ever been satisfied by someone who did something you didn't like but said "I was just following the rules"?

Even strict rules tend to have an out, like a petition to take a set of courses that don't exactly match the requirements of a major. The petition is a standard, open to interpretation to capture what the rules don't. 

As a complexity theorist I know what programs can't achieve, and as an administrator I see the same with rules. I prefer standards, principles over policies. Set your expectations, live by example, and trust the people, faculty, staff and students, to do the right thing and push back when they don't. People don't want strict rules, but they mostly act properly when they believe they are trusted and have wide latitude in their work. 

Complexity theory of hand-calculations

 (Thanks to David Marcus who sent me the video I point to in point 4 of this post. Tip for young bloggers (if there are any) you can have a half-baked idea for a post and then someone sends you something OR you later have an idea to make it a full-baked idea for a post. That's what happened here. So keep track of your half-baked ideas.)

1) When I was 10 years old I wanted to find out how many seconds were in a century. I didn't have a calculator (I might not have known what they were). I spend a few hours doing it and I got AN ANSWER. Was it correct? I didn't account for leap years. Oh well.

(An astute reader pointed to a website that does the centuries-to-seconds conversion as well as many other conversions. It is here. If such was around when I was a kid, what affect would it have on my interest in math? Impossible to know.) 

2) Fast forward to 2024: I wanted to find the longest sequence of composites all \( \le 1000\). One long sequence I found by hand is the following (I also include the least prime factor):

114-2, 115-5, 116-2, 117-3, 118-2, 119-7, 120-2, 121-11, 122-2, 123-3, 124-2 , 125-5, 126-2

length 13.

I wanted to find the answer WITHOUT using a computer program or looking at list of primes online (though I do allow a calculator just for division and multiplication). 

Of more interest mathematically is trying to prove that there is no sequence of length 14. (If there is, then perhaps the attempt will lead us to it.) 

Assume there was a sequence of consecutive composites \(\le 1000\) of length 14.

Map each one to the least prime that divides it. 

At most 7 of them map to 2

At most 3 of them map to 3

At most 2 of them  map to 5

At most 1 of them  map to 7.

At most 1 maps to 11. (Can look at 11*p for all primes \(11\le p \le 89\) and see any of them are in a sequence of length 14.) 

I'll stop here. This is getting tedious and might be wrong. So I asked Claude. It gave me a  sequence of composites of length 19. Here it is (I include the least prime factor):

888-2, 889-7, 890-2, 891-3, 892-2, 893-19, 894-2, 895-5, 896-2, 897-3, 898-2, 899-29, 900-2, 901-17, 902-2, 903-3, 904-2, 905-5, 906-2.

Can one show by hand that there is no sequence of length 20? 

3) The more general question: what is the complexity of finding the longest string of composites all \( \le n\) . This is actually many questions:

a) By hand: by which I mean only allowing multiplication and division and only of numbers \(\le n.\)

b) Theoretically. Use whatever fancy algorithms you want.

c) Theoretically but can assume some Number theory Conjectures that are widely believed. The Wikipedia page on prime gaps is here. (ADDED LATER- an astude commenter pointed out that we want LARGE gaps between primes, but the wikipedia article is about SHORT gaps between primes.) 

d) Do a,b,c for the set version which is as follows:  Given \(n\) and\( L\) determine if there a sequence of consecutive composites of length L that are all \(\le n\).  

4) Does anyone else care about calculation-by-hand? Yes! There are people who want to compute\(\ pi\) to many places JUST BY HAND. Here is a video about them here. Spoiler alert: they did very well. 

The Hilltop Story

 

On Route 1 in Saugus, Massachusetts, about a twenty minute drive from Cambridge, stood the Hilltop Steak House. When I went to graduate school in the late 80's, Hilltop led all restaurants in the United States by sales (about $30 million in annual revenue) and volume (about 2.5 million customers).

I went there several times during graduate school. Despite the size, about 1500 seats, always a long wait but worth it to get a good steak at a price a grad student could afford. 

But in 1994, Hilltop was bought by an investment company from the original Giuffrida family. The cost of labor went up and to keep costs reasonable, the new owners cut the quality of the meat. No longer a place to get good steak at a good price and with changing tastes, they lost customers and would finally close in 2013.

Computer Science as an academic discipline has had its Hilltop moment with tremendous growth pretty consistently from 2010 through about 2023. But with the growth of AI and an uncertain job market, if we don't maintain quality and adjust to the new needs and interests of our students, CS may become just a road sign on Route 1.

Some are Mathematicians, some are Carpenters' Wives, Some are Popes.

 (Trivia: What song has the lyric Some are Mathematicians, some are Carpenters's wives ? It's not a parody song, though sometimes it's hard to tell a  parody song from a so-called real song.)

In my post about Pope Leo XIV I made the following comments in different parts of the post:

Pope Leo XIV has a degree in Mathematics.

Prevost [his pre-Pope name] has a degree in mathematics from Villanova. 

He is not the first Pope to know some mathematics.

I also wrote:

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

Someone emailed me about this line, not to say it was a bad joke or even a good joke, but to say 

Since Pope Leo XIV was a mathematician: What qualifies one to be considered a mathematician?

A few thoughts on this question.

1) I blogged about this topic here. Hence today I will discuss issues I did not discuss then. 

2) Robert W  Prevost wrote a book that (just from the title) seems to use some math:

Probability and Theistic Explanations, see here.

that was published in print in 1990 and online in 2023.  I wonder if it will sell more copies now.  I am tempted to ask for a free copy to read and do a review of, but I'm not sure I really want to read it. 

One would think that if someone named Robert Prevost wrote a book that seems to use math and theology then it would be the Robert Prevost who is now called Pope Leo XIV. I thought that. A commenter on my blog thought that. But Lance read an earlier version of this post and pointed out that 

Robert W Prevost NE Robert  F Prevost AND

Robert F  Prevost = Pope Leo XIV.

Hence, alas, the author of the book is NOT Pope Leo XIV. It's striking how plausible it would be that Pope Leo IS the author.  The book STILL might sell more copies since people may think it's by the Pope. 

Robert W Prevost's Wikipedia page is here.

Robert F Prevost's Wikipedia page is here.

3) If someone keeps LEARNING math but doesn't DO math I WOULD consider them a mathematician.

4) If someone is a math crank then the question of are they a mathematician will depend on how cranky they are.

5) If one KNOWS a lot of math but is neither learning anymore or doing any more (perhaps myself when I retire) can you consider them a mathematician?

6) If someone gets a PhD from MIT in Pure math but then goes to industry and programs would you consider them to be a mathematician?

7) If X is NOT a math crank and X considers themselves a mathematician, are they a mathematician?

8) I WOULD consider applied math to be math. This should not need to be said but there may be some pure-math-snobs reading this post. Computer scientists, statisticians, are more of a borderline case that, without being a snob, I might not consider mathematicians.

9)  Someone posted on the blog where this came up Does Lance consider himself a mathematician? I asked Lance and he said:

For the next 37 days I consider myself a Dean. After that, who knows?

The Blog of Record

On Saturday, I had my last Illinois Tech graduation as dean before I step down at the end of June. The College of Computing had nearly 1600 graduates and I shook many, many hands that morning.

After graduation I caught a plane to Washington, DC to attend the wedding of my daughter's college friend. We were invited because we became good friends with the bride's parents when we lived in Atlanta. My last trip before Covid was to DC for an NSF panel and this was my first trip to Washington since. 

The out-of-town guests were housed at the Hyatt Regency Bethesda, coincidentally the same hotel that hosted STOC 2009. My favorite STOC talk of all time took place in that building. But I remembered nothing about the venue except for the jogging path near the hotel.

No trip to the DMV would be complete without seeing my co-blogger Bill Gasarch in person for the first time in years. We chatted about many things, most notably his last few posts where he joked about the new pope's undergraduate math thesis, taken seriously by both our readers and ChatGPT. I reminded Bill that we are the blog of record, often used by wikipedia as a primary source for much in and out of complexity. Later Bill took out the fake thesis titles.

With graduation behind me, not much more for me to do as dean before my term ends. On the plane ride home, I thought about the question everyone asks me: What's next? I have no idea, but it's going to be fun.

Is Satire Dangerous in the AI-Age?

There have been times when satire has been mistaken for reality. A list of Onion stories that were mistaken for reality (or was it a mistake?) is here. When I say mistaken for reality I mean that a large set of people were fooled.

My own Ramsey-History-Hoax (blog here, latest version of the paper here) has fooled some people; however the number of people is small since the number of people who know the underlying math is small. 

In my last blog (see here) I said that the Pope Leo XIV majored in math (that is true) and then I gave a false title for his thesis (I HAVE SINCE REMOVED THE ENTIRE PASSAGE). 

 Later in the post I said that his ugrad thesis was not on that topic, but  gave another false title (I HAVE RMEOVED THAT AS WELL.) 

I thought the reader would know that it was false, but one comment inquired about it so I left a comment admitting it was false.

This is all very minor: Not that many people read this blog and very few non-math people would care about what the topic of the  Pope's undergraduate thesis.

The last part of the last sentence is false. Its the POPE! People Do care about his background. 

But surely my blog post isn't so well read so as to make the fictional  title of his thesis a hoax that fools a lot of people. 

Even so, I left a comment wondering if LLM's might learn the incorrect title of the Pope's ugrad thesis. 

A reader named E posted the following:

 It might be too late. I did this search this evening:

E: Did Pope Leo XIV study Ramsey Theory?

Gemini: Pope Leo XIV, whose given name is Robert Francis Prevost,
earned a Bachelor of Science degree in mathematics from Villanova
University in 1977. His undergraduate thesis focused on Rado's Theorem
for Nonlinear Equations.

0) This may not be too bad- one would have to ask about The Pope and Ramsey Theory to get that answer. But in the future this answer might pop up on the question`What did the Pope Study as an Undergraduate' or similar questions.

1) Might future satires or April Fool's Day jokes be mistaken for reality in the future by AI and hence reach a much larger audience than this blog does?

2) If so, should we be careful with what we post (not sure how to do that)?

3) What about people who have a much larger following than complexityblog  (yes, there are such people)?

4) In the past one had to be a celebrity or similar to change peoples perception of reality (see Stephen Colbert and Wikipedia here). Now a complexity blogger may be able to change people's perception of reality. Hence I ask

Is Satire Dangerous in the AI-Age?

 

 

 

 

 

A Bittersweet Anniversary

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.

Random Thought on the New Pope (the actual New Pope, not the TV series). He was a math major!

 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.  (NOTE- I USED TO HAVE A TITLE OF THE POPE'S UGRAD MATH THESIS, WHICH WAS FAKE, BUT SINCE AI'S PICKED IT UP AS REAL I HAVE DELETED THAT, AND ALSO DELETED A LATER PART OF THIS POST WHERE I  GIVE THE REAL TITLE, WHICH IS ALSO FAKE.)

Prevost earned a Bachelor of Science (BS) degree in mathematics from Villanova University, an Augustinian college, in 1977.  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. 

11) Trump thinks that since the Pope is American, America should annex the Vatican. Or does he? See this article here.  

12) Pope Leo has an opinion about AI (I wonder if his math background helps); see here. This is a good example of the limits to the Pope's power-does anyone who can do anything care what Pope Leo XIV thinks? I ask non-rhetorically as always.