(Sung to the tune of «Supercalifragilisticexpialidocious.»)
Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!
Superpolylogarithmic subexponential functions!
Faster than a polylog but slower than exponential.
Even though they’re hard to say, they’re truly quintessential.
Superpolylogarithmic subexponential functions!
Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!
For Alice to send a message through to Bob when Eve’s eavesdropping,
Do use a trapdoor one-way function—not a one-key mapping.
First take a message x, let’s say, and raise it to the e;
Then mod it out by p times q but keep these secretly. Oh!
(Chorus)
Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!
The process takes but poly-time and appears to be secure:
Why even just a single bit is one over polylog pure.
Though Alice thinks that Eve must spend time at least exponential,
By using Lenstra’s elliptic curves, Eve splits n subexponentially. Oh!
(Chorus)
Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!
Most computations dissipate a lot of energy;
We remove the heat with water but there’s a better strategy.
Since thermodynamics does not apply when info is not doomed,
The laws of physics don’t require that power be consumed. Oh!
(Chorus)
Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!
Now Bennett said in `73, to run a program P,
You simulate the program P, but do so reversibly.
The problem with this method is that space is exponential,
So trade off time to save on space—this really is essential! Oh!
(Chorus)
Um diddle diddle diddle, um diddle ay!
Um diddle diddle diddle, um diddle ay!
Did you know if you invert one, you get a
Funtionential subexporithmic logapolyrepus?
But that’s quite a singularity! So,
If you are in an oral exam and cannot find the way,
Just summon up these words and then you’ve got a lot to say.
But better use them carefully or you could fail the test.
A professor once asked me,
«What do you call functions that grow faster than any
Polylogarithm but slower than exponential?» There’re,
Superpolylogarithmic subexponential functions!
Superpolylogarithmic subexponential functions!
Superpolylogarithmic subexponential functions!
Superpolylogarithmic subexponential functions!
Note: See paper for detailed performance notes and mathematical
Proofs by anagramming.
