The Godzilla Moment

On the plane earlier this week I got around to watching the Academy Award winning movie Godzilla Minus One, one of the best monster movies I've seen set in Japan during the aftermath of World War II, with a pretty emotional substory about a man dealing with his demons from the war. I had to hide my tears from the nearby passengers.

It wasn't the story that earned the movie an Oscar. Godzilla Minus One won the awards for Best Visual Effects. I found nothing wrong with the effects, but they didn't excel beyond what you see in any typical movie of the genre.

In 2008, I lamented that special effects in movies had improved so much that we had lost the amazement we felt in the 70s. Perhaps I spoke too soon, as James Cameron's Avatar came out the following year and did amaze. However, special effects have since become a commodity, something filmmakers must include because audiences expect it but rarely do you go to a movie for the effects. In the not-too-distant future, special effects will be automated with AI, becoming just another plugin for Final Cut Pro. 

It's time to retire the visual effects award, especially with new awards coming to the Oscars.

I wrote that 2008 column to mirror the lack of enthusiasm about computing at the time which also felt like a commodity. Now we're at an exciting time in computing particularly with the advances in artificial intelligence. But we should be wary, once (if?) AI gets consistently good it may feel like a commodity again and once again we become victims of our own success. 

FOCS 2024 Test of Time Award. Call for nominations and my opinion

 The call for nominations for the Test of Time Award at FOCS 2024 has been posted here.

Eligibility and past winners are here.

Points

1) It is good to have an award that waits until the dust settles and we can see what was really important.

2) The winners are all excellent papers that really have passed the test of time. 

3) And of course it is really important that they appeared in FOCS. NO IT ISN"T! See next point

4) I would prefer a test-of-time award that is independent of WHERE the paper first appeared. Tying it to FOCS or STOCS or FOCS-or-STOC seems bad. I would opt for appearing in ANY journal or conference. Appearing in a journal of low quality is not a problem since this award should be  for papers that are judged on their merit and influence, and not on their pedigree.

5) My proposal to allow any journal or conference may be impractical because some organization has to give it out, and if that organization is IEEE or ACM they will restrict to their own publications. 

6) STOC also has a test of time award, see here 76) I tried to find out of the SODA conference has a test of time award but mostly got hits about the Baking Soda Test for determining if a pregnant women is going to have a boy or  girl. It actually worlds 50% of the time! See here

7) I was not able to find any other test-of-time award for Comp Sci THEORY. 

8) I DID find test of time awards for

SIGCSE- Comp Sci Education, here. Must be for a paper published in a conference co-sponsored by SIGCSE or in an ACM journal.  So an excellent paper published elsewhere wouldn't count. 

SC2- High Performanc Computing, see here. Paper must have been published in the SC conference. 

ACM CCS - Security, Audit(?) and Control, see here I think these must appear in the CCS conference. 

Double Digit Delights

It started with a post from Fermat's Library.

132 is the sum of all the 2-digit numbers made from its digits. It is the smallest such number. pic.twitter.com/hrByAXbr51

— Fermat's Library (@fermatslibrary) May 26, 2024

My immediate reaction was why not list them all? Giving the smallest such number suggests there are an infinite number of them. But the value of a d-digit number grows exponentially in d, while the 2-digit sum grows quadratically so there must only be a finite number. 

Let's be a little more formal. Let's restrict ourselves to positive integers with no leading zeros. The 2-digit sum of x is the sum of all 2-digit numbers formed by concatenating the ith digit of x and the jth digit of x for all i,j with i\(\neq\)j. The 2-digit sum of 132 is 13+12+31+32+21+23 = 132. The 2-digit sum of 121 is 12+11+21+21+11+12 = 88. A number x if 2-idempotent if the 2-digit sum of x is x.

Let's look at the possible lengths of 2-idempotent numbers.

For 1-digit numbers the 2-digit sum is zero.

For 2-digit numbers the 2-digit sum is that number plus another positive number so never equal.

For 5-digit numbers, the 2-digit sum is bounded by 20*99 = 1980 < 10000. So there are no 2-idempotent numbers with 5-digits. More than 5 digits can be discarded similarly. 

For 4-digit numbers, the two digit sum is at most 12*99 = 1188. So a 2-idempotent number must begin with a one. Which now bounds it by 19*3+91*3+99*6=924. So there are no 2-idempotent numbers of 4 digits.

So every 2-idempotent must have 3 digits. I wrote up a quick Python program and the only three 2-idempotents are 132, 264 and 396. Note that 264 is 2*132 and 396 is 3*132. That makes sense, if you double every digit and don't generate carries, every two-digit part of the sum also doubles.

Biscuit asks if there is some mathematical argument that avoids a computer or manual search. You can cut down the search space. Every length 3 2-idempotent is bounded by 6*99=594 and must be even since every digit appears in the one's position twice. But I don't know how to avoid the search completely.

Two more Python searches: 35964 is the only 3-idempotent number. If you allow leading zeros then 0594 is 2-idempotent. There may (or may not) be infinitely many such numbers.

National BBQ day vs World Quantum Day

 After my post on different holiDAYS, here, such as Talk like a Pirate Day, and Raegan Revor day, two other Days were brought to my attention

1) Lance emailed me about National BBQ day, which is May 16. See here

2) While at a Quantum Computing Prelim I saw a poster for World Quantum Day, which is April 14. See here.

The obvious question: Which of these days is better known? I Googled them again but this time note the number of hits. 

I found out that Google seems to have removed that feature!

When using Google on both Firefox and Chrome, I did not get number of hits. 

Some points about this

1) Is there a way to turn the number-of-hits feature on?

2) Bing DOES give number of hits.

World Quantum Day: 899,000 hits

National BBQ Day: 418,000 hits

To get a baseline I binged Pi Day. This did not reveal the number of hits. An unscientific set of Bing searches seems to indicate that if the number of hits is large then they are not shown.

Is hits-on-Bing a good measure of popularity? I do not know.

3) Duck Duck Go does not give number of hits. This might be part of their privacy policy.

4) I also noticed a while back that You Tube no longer allows DISLIKES, just likes. That may explain why my Muffin Math song on You Tube (see here), with Lance on the Piano,  has 0 dislikes. It does not explain why it got  19 likes.

5) Google said that the number-of-hits is really an approximation and one should not take it too seriously. 

YouTube said that (not in these words) the haters caused dislikes to be far more than they should be.

On the one hand, I want to know those numbers. On the other hand I think Google and YouTube are right about about the numbers not being that accurate. And more so for Bing which is used less so (I assume) has less data to work from.

6) Back to my question: What is better known National BBQ day or World Quantum Day? The nation and the world may never know. 

7) All of the above is speculation.

Peer Review

Daniel Lemire wrote a blog post Peer Review is Not the Gold Standard in Science. I wonder who was claiming it was. There is whole section of an online Responsible Conduct in Research we are required to take on peer review which discussing its challenges: "honesty, objectivity, quality control, confidentiality and security, fairness, bias, conflicts of interest, editorial independence, and professionalism". With apologies to Winston Churchill, Peer Review is the worst form of measuring academic quality, except for all of the others.

Peer review requires answering two questions.

1. Has the research been done properly?
2. What is the value of the research?

For theoretical research, the first comes down to checking the proofs, which sounds like an objective check. Here we have a "gold standard", formalizing the proof so it can be verified in a proof system like Lean. That's a heavy burden so we generally only require authors to give enough details so it's clear that we could formalize the proof given enough time. That becomes subjective and reviewers, especially for conferences, may not have the time or inclination to check the details of a 40-page proof. Maybe one day AI can take a well-written informal proof and formalize it for a proof system.

But the second question is almost entirely subjective. How does the work advance previous research? What value does it give to a field and how does it set up future research? Different researchers will give different opinions. And then there are the people who consciously or unconsciously cheat, helping their friends get papers accepted to citations rings. As we focus on metrics to judge researchers, too many people will game the system to pump up those metrics.

In 2013, NeurIPS had over 13,000 submission for 3500 slots. Even with the best or reviewer's intentions, it's impossible to maintain any sense of consistency for these large volume conferences.

Despite the problems with peer review, you'd hate to us a different system, say delegating the reviewing to some AI process, even if it could lead to more consistency. I suspect many reviews are being delegated anyway.

Peer review grew in importance as journals and conferences had to make choices to fill a limited proceedings. These days we have the capacity to distribute every papers. So perhaps the best form of measuring academic quality is no review at all.

I don't do that well when the Jeopardy category is Math

Bill and Darling are watching Jeopardy.

DARLING: Bill, one of the categories is MATH TALK. You will kick butt!

BILL: Not clear. I doubt they will have the least number n such that R(n) is not known. They will ask things easy enough so that my math knowledge won't help.

DARLING: But you can answer faster.

BILL: Not clear. 

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

Recall that in Jeopardy they give the answers and you come up with the question.

Like Sheldon Cooper I prefer my questions in the form of a question. 

Even so, I will present the answers that were given on the show (that sounds funny), then 

I will provide the questions (that sounds funny), what happened, and what I would have gotten right. 

$400

ANSWER: Its a demonstrably true mathematical statement; Calculus has a ``Fundamental'' one.

QUESTION: What is a Theorem?

WHAT HAPPENED: Someone buzzed in and said AXIOM. This one I knew the answer and would have won!

$800

ANSWER: Fire up the engines of your mind and name this solid figure with equal and parallel circles at either end. 

QUESTION: What is a Cylinder?

WHAT HAPPENED: Someone buzzed in with the correct answer. I had a hard time parsing this one and only got it right in hindsight. This one I would have lost on. Note that the phrase Fire up your engines is supposed to make you think of Fire on all cylinders. This did not help me.

$1200

ANSWER: Multiply the numerator of one fraction by the denominator of another (and vice versa) to get the ``cross'' this. 

QUESTION: What is a Product?

WHAT HAPPENED: I got this one very fast. So did the contestant on the real show. Not clear what would happened if I was there.

$1600

ANSWER: See if you can pick off this term for the point at which a line or curve crosses an axis. 

QUESTION: What is an Intercept?

WHAT HAPPENED: Someone buzzed in with the correct answer. I really didn't know what they were getting at. Even in hindsight the answer does not seem right, though I am sure that it is. The phrase pick off this term is  supposed to remind me of something, but it didn't. Lance happened to read a draft of this post and did the obvious thing: asked ChatGPT about it. ChatGPT said that in football a pick off is an interception. To see the ChatGPT transcript see here.

$2000

ANSWER: In 19-5=14 19 is the minuend; 5 is this other ``end''

QUESTION: What is a  Subtrahend?

WHAT HAPPENED: Someone buzzed in with the correct answer. The answer was news to me. It is correct; however, I am not embarrassed to say I never heard these terms. Spellcheck thinks that minuend and subtrahend words. This is similar to when I was not smarter than a fifth grader (see blog post here). 

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

So the final tally:

The $400 question I would have gotten right

The $1200 question I might have gotten right if I was fast on the buzzer

But that's it. Why did I do so badly? 

1) Two of the ones I got wrong were phrased in funny ways. I thought so anyway. And note that they did not use advanced math knowledge, so my math knowledge didn't help. (This is not a complaint- it would be bad if they used advanced math knowledge. Like when a crossword puzzle my wife was working on wanted  Log-Man and it began with N and I knew Napier. Why was that in a crossword puzzle for laypeople? Because  Napier has a lot of vowels in it.)

2) One of them I really did not know the math knowledge. Is it arrogant to say that if there is a math question on Jeopardy where I don't know the answer then its a bad question? I leave that as an exercise for the reader. 

On questions about  presidents, vice presidents, or American history, I do well.

On questions about novelty songs  (sometimes comes up) I do very well. (One question was about this song here. The question: here.)

But math... not so much. 

For computer science questions I also do not do that well, but I've learned some common abbreviations that I did not know: 

BIT: Binary Integer (A reader named Anonymous, who makes many comments, pointed out that BIT is actually Binary Digit. I have a possibly false memory of Jeopardy telling me Binary Integer. Either my memory is wrong or Jeopardy is wrong. But Anonymous is right- its Binary Digit.) 

HTTP: Hypertext Transfer Protocol

HTML: Hyper Text Markup Language

FORTRAN: Formula Translation

Those were more interesting than learning about minuend and subtrahend, terms I had never heard before and won't hear again unless I catch a rerun of Jeopardy (at which time I will get it right).

Jim Simons (1938-2024)

Jim Simons passed away Friday at the age of 86. In short he was a math professor who quit to use math to make money before it was fashionable and used part of his immense wealth to start the Simons Foundation to advance research in mathematics and the basic sciences.

While his academic research focused on manifolds, Simons and his foundation had theoretical computer science as one of its priorities and helped fund and promote our field on several fronts.

Foremost of course is the Simons Institute, a center for collaborative research in theoretical computer science. Announced as a competition in 2010 (I was on team Chicago) with the foundation eventually landing on UC Berkeley's campus. At the time, I wrote "this will be a game changer for CS theory" if anything proven to be an understatement over the last dozen years.

Beyond the institute, the Simons Foundation has funded a number of theorists through their investigator and other programs.

Let's not forget Quanta Magazine, an online science publication funded by the foundation without subscriptions or paywalls while science journalism has been seeing cuts elsewhere. Quanta has been particularly friendly to the computational complexity community such as this recent article on Russell and his worlds.

The Simons Foundation will continue strong even without its founder. But as we see challenges in government funding, how much can or should we count on wealthy patrons to support our field?

Read more on Jim Simons from Scott, Dick, the foundation and the institute.

What is Closed Form? The Horse Numbers are an illustration

In the book Those Fascinating Numbers by Jean-Marie De Konick they find interesting (or `interesting') things to say about many numbers. I reviewed the book in a SIGACT News book review column here. The entry for 13 is odd: 13 is the third Horse Number.  The nth Horse number is the number of ways n horses can finish a race. You might think: OH, that's just n!. AH- horses can tie. So it's the number of ways to order n objects allowing ties. 

Is there a closed form for H(n)? We will come back to that later. 

0) The Wikipedia Entry on horse races that ended in a dead  heat is here. They list 78 dead heats (two horses tie for first place) and 10 triple dead heats (three horses tie for first place). For the horse numbers we care if (say) two horses tie for 4th place. In reality nobody cares about that. 

1) I have found nowhere else where these numbers are called The Horse Numbers. 

2) They are called the Ordered Bell Numbers. The Wikipedia entry here has some applications.

3) They are also called the Fubini Numbers according to the Ordered Bell Number Wikipedia page.

4) I had not thought about the Horse Numbers for a long time  when they came up while I was making slides for the proof that  (Q,<) is decidable (the slides are here).

5) There is an OEIS page for the Horse Numbers, though they are called the Ordered Bell Numbers and the Fubini Numbers. It is here. That page says H(n) is asymptotically \(\frac{1}{2}n!(\log_2(e))^{n+1}\) which is approx \(\frac{1}{2}n!(1.44)^{n+1}\).

6) There is a recurrence for the Horse Numbers:

H(0)=1

H(1)=1

H(2)=3

For all  \(n\ge 3\) we split H(n) into what happens  if i horses are tied for last place (choose i out of n) and if the rest are ordered H(n-i) ways. Hence

\( H(n) = \binom{n}{1}H(n-1) + \binom{n}{2}H(n-2) +  \cdots  + \binom{n}{n}H(0) \)

Using \(\binom{n}{i} = \binom{n}{n-i}\) we get

\( H(n) = \binom{n}{0}H(0) + \binom{n}{1}H(1) +  \cdots  + \binom{n}{n-1}H(n-1) \)

STUDENT: Is there a closed form for H(n)?

BILL: Yes. Its H(n).

STUDENT: That's not closed form.

BILL: Is there a closed form for the number of ways to choose i items out of n?

STUDENT: Yes, \(\binom{n}{i}\) or \( \frac{n!}{i!(n-i)!}\) 

BILL: Does that let you compute it easily? No. The way you compute \(\binom{n}{i}\) is with a recurrence. The way you compute H(n) is with a recurrence. Just having a nice notation for something does not mean you have a closed form for it. 

STUDENT: I disagree! We know what n! is!

BILL: Do not be seduced by the familiarity of  the notation.