A commenter on my last post writes:

Scott, it’s your blog - but can’t we switch back to some QC or TCS topics?

I confess: after three years of staid, dignified posts about quantum computing and theoretical computer science, I somehow did the unthinkable, and let this once-respected blog become less about elucidating research than procrastinating from it.  Many readers, or so they tell me, rely on Shtetl-Optimized to keep abreast of the latest theoretical insights.  And rather than ask those readers whether they also rely on deep-fried Snickers bars for the Vitamin E in the peanuts, I have a moral obligation to serve them.

Fortunately for the theory-starved among you, a certain je ne sais quoi in the air last week has caused me to refocus my attention on research.  The mysterious force affected not only me, but seemingly my entire floor of the Stata Center—giving rise to a carnival-like crescendo of increasingly-frantic theorizing that ended just as inexplicably as it began, around 6:59PM Thursday night.

So today, I’m proud to post something vaguely related to science once again.  On the suggestion of Wim van Dam, I hereby announce another contest, with no prize or even possibly winner.  Your task is simple:

Come up with a catchy name for growth rates of the form 2^{n^α}, 0<α<1.

(For example, the running time of the fastest known classical factoring algorithm has this form, as does that of the fastest known algorithm for graph isomorphism.)

The word “subexponential” is often used, but should not be, since we already use it for growth rates smaller than 2^{n^α} for all α>0.

This just in: Friend-of-the-blog Greg Kuperberg, who’s always more fun than a cinder block combined with a reprimand, informs me that 2^{n^α} growth rates already have a name: stretched exponentials.  But

1. I’ve never heard that term in my life,
2. I don’t like it: it sounds like something bigger than exponential, not smaller, and
3. Having called 2^√n “subexponential” in his otherwise-great paper on a quantum algorithm for the Dihedral Hidden Subgroup Problem, for Greg to now lecture others on this issue seems like … stretching it.

So my and Wim’s challenge to the readerariat stands.