{"id":394,"date":"2009-04-05T01:20:33","date_gmt":"2009-04-05T05:20:33","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=394"},"modified":"2009-04-05T01:20:33","modified_gmt":"2009-04-05T05:20:33","slug":"a-not-quite-exponential-dilemma","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=394","title":{"rendered":"A not-quite-exponential dilemma"},"content":{"rendered":"

A commenter on my last post<\/a> writes:<\/p>\n

Scott, it\u2019s your blog – but can\u2019t we switch back to some QC or TCS topics?<\/p><\/blockquote>\n

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.\u00a0 Many readers, or so they tell me, rely on Shtetl-Optimized<\/em> to keep abreast of the latest theoretical insights.\u00a0 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.<\/p>\n

Fortunately for the theory-starved among you, a certain je ne sais quoi<\/em> in the air last week has caused me to refocus my attention on research.\u00a0 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.<\/p>\n

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

Come up with a catchy name for growth rates of the form 2n^\u03b1<\/sup>, 0<\u03b1<1.<\/em><\/p>\n

(For example, the running time of the fastest known classical factoring algorithm<\/a> has this form, as does that of the fastest known algorithm for graph isomorphism<\/a>.)<\/p>\n

The word “subexponential” is often used, but should not<\/em> be, since we already use it for growth rates smaller than 2n^\u03b1<\/sup> for all \u03b1>0.<\/p>\n

This just in:<\/font><\/strong> Friend-of-the-blog Greg Kuperberg, who’s always<\/em> more fun than a cinder block combined with a reprimand, informs me that 2n^\u03b1<\/sup> growth rates already have a name: stretched exponentials<\/a>.\u00a0 But<\/p>\n

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

    So my and Wim’s challenge to the readerariat stands.<\/p>\n

    <\/p>\n","protected":false},"excerpt":{"rendered":"

    A commenter on my last post writes: Scott, it\u2019s your blog – but can\u2019t 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,14,30],"tags":[],"class_list":["post-394","post","type-post","status-publish","format-standard","hentry","category-complexity","category-contests","category-mirrored-on-csail-blog"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/394","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=394"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/394\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=394"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=394"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=394"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}