CINXE.COM

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" lang="en-US"> <head profile="http://gmpg.org/xfn/11"> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <title>Shtetl-Optimized » 2007 » August</title> <meta name="generator" content="WordPress 6.7.2" />  <link rel="stylesheet" href="https://149663533.v2.pressablecdn.com/wp-content/themes/ohmygod/style.css" type="text/css" media="screen" /> <link rel="alternate" type="application/rss+xml" title="Shtetl-Optimized RSS Feed" href="https://scottaaronson.blog/?feed=rss2" /> <link rel="pingback" href="https://scottaaronson.blog/xmlrpc.php" /> <style type="text/css" media="screen"> #page { background: url("https://149663533.v2.pressablecdn.com/wp-content/themes/ohmygod/images/kubrickbg-ltr.jpg") repeat-y top; border: none; } </style> <meta name='robots' content='max-image-preview:large' /> <style>img:is([sizes="auto" i], [sizes^="auto," i]) { contain-intrinsic-size: 3000px 1500px }</style> <link rel='dns-prefetch' href='//stats.wp.com' /> <link rel='dns-prefetch' href='//v0.wordpress.com' /> <link rel='preconnect' href='//c0.wp.com' /> <script type="text/javascript"> /* <![CDATA[ */ window._wpemojiSettings = {"baseUrl":"https:\/\/s.w.org\/images\/core\/emoji\/15.0.3\/72x72\/","ext":".png","svgUrl":"https:\/\/s.w.org\/images\/core\/emoji\/15.0.3\/svg\/","svgExt":".svg","source":{"concatemoji":"https:\/\/scottaaronson.blog\/wp-includes\/js\/wp-emoji-release.min.js?ver=6.7.2"}}; /*! This file is auto-generated */ !function(i,n){var o,s,e;function c(e){try{var t={supportTests:e,timestamp:(new Date).valueOf()};sessionStorage.setItem(o,JSON.stringify(t))}catch(e){}}function p(e,t,n){e.clearRect(0,0,e.canvas.width,e.canvas.height),e.fillText(t,0,0);var t=new Uint32Array(e.getImageData(0,0,e.canvas.width,e.canvas.height).data),r=(e.clearRect(0,0,e.canvas.width,e.canvas.height),e.fillText(n,0,0),new Uint32Array(e.getImageData(0,0,e.canvas.width,e.canvas.height).data));return t.every(function(e,t){return e===r[t]})}function u(e,t,n){switch(t){case"flag":return n(e,"\ud83c\udff3\ufe0f\u200d\u26a7\ufe0f","\ud83c\udff3\ufe0f\u200b\u26a7\ufe0f")?!1:!n(e,"\ud83c\uddfa\ud83c\uddf3","\ud83c\uddfa\u200b\ud83c\uddf3")&&!n(e,"\ud83c\udff4\udb40\udc67\udb40\udc62\udb40\udc65\udb40\udc6e\udb40\udc67\udb40\udc7f","\ud83c\udff4\u200b\udb40\udc67\u200b\udb40\udc62\u200b\udb40\udc65\u200b\udb40\udc6e\u200b\udb40\udc67\u200b\udb40\udc7f");case"emoji":return!n(e,"\ud83d\udc26\u200d\u2b1b","\ud83d\udc26\u200b\u2b1b")}return!1}function f(e,t,n){var r="undefined"!=typeof WorkerGlobalScope&&self instanceof WorkerGlobalScope?new OffscreenCanvas(300,150):i.createElement("canvas"),a=r.getContext("2d",{willReadFrequently:!0}),o=(a.textBaseline="top",a.font="600 32px Arial",{});return e.forEach(function(e){o[e]=t(a,e,n)}),o}function t(e){var t=i.createElement("script");t.src=e,t.defer=!0,i.head.appendChild(t)}"undefined"!=typeof Promise&&(o="wpEmojiSettingsSupports",s=["flag","emoji"],n.supports={everything:!0,everythingExceptFlag:!0},e=new Promise(function(e){i.addEventListener("DOMContentLoaded",e,{once:!0})}),new Promise(function(t){var n=function(){try{var e=JSON.parse(sessionStorage.getItem(o));if("object"==typeof e&&"number"==typeof e.timestamp&&(new Date).valueOf()<e.timestamp+604800&&"object"==typeof e.supportTests)return e.supportTests}catch(e){}return null}();if(!n){if("undefined"!=typeof Worker&&"undefined"!=typeof OffscreenCanvas&&"undefined"!=typeof URL&&URL.createObjectURL&&"undefined"!=typeof Blob)try{var e="postMessage("+f.toString()+"("+[JSON.stringify(s),u.toString(),p.toString()].join(",")+"));",r=new Blob([e],{type:"text/javascript"}),a=new Worker(URL.createObjectURL(r),{name:"wpTestEmojiSupports"});return void(a.onmessage=function(e){c(n=e.data),a.terminate(),t(n)})}catch(e){}c(n=f(s,u,p))}t(n)}).then(function(e){for(var t in e)n.supports[t]=e[t],n.supports.everything=n.supports.everything&&n.supports[t],"flag"!==t&&(n.supports.everythingExceptFlag=n.supports.everythingExceptFlag&&n.supports[t]);n.supports.everythingExceptFlag=n.supports.everythingExceptFlag&&!n.supports.flag,n.DOMReady=!1,n.readyCallback=function(){n.DOMReady=!0}}).then(function(){return e}).then(function(){var e;n.supports.everything||(n.readyCallback(),(e=n.source||{}).concatemoji?t(e.concatemoji):e.wpemoji&&e.twemoji&&(t(e.twemoji),t(e.wpemoji)))}))}((window,document),window._wpemojiSettings); /* ]]> */ </script> <style id='wp-emoji-styles-inline-css' type='text/css'> img.wp-smiley, img.emoji { display: inline !important; border: none !important; box-shadow: none !important; height: 1em !important; width: 1em !important; margin: 0 0.07em !important; vertical-align: -0.1em !important; background: none !important; padding: 0 !important; } </style> <link rel='stylesheet' id='wp-block-library-css' href='https://c0.wp.com/c/6.7.2/wp-includes/css/dist/block-library/style.min.css' type='text/css' media='all' /> <link rel='stylesheet' id='mediaelement-css' href='https://c0.wp.com/c/6.7.2/wp-includes/js/mediaelement/mediaelementplayer-legacy.min.css' type='text/css' media='all' /> <link rel='stylesheet' id='wp-mediaelement-css' href='https://c0.wp.com/c/6.7.2/wp-includes/js/mediaelement/wp-mediaelement.min.css' type='text/css' media='all' /> <style id='jetpack-sharing-buttons-style-inline-css' type='text/css'> .jetpack-sharing-buttons__services-list{display:flex;flex-direction:row;flex-wrap:wrap;gap:0;list-style-type:none;margin:5px;padding:0}.jetpack-sharing-buttons__services-list.has-small-icon-size{font-size:12px}.jetpack-sharing-buttons__services-list.has-normal-icon-size{font-size:16px}.jetpack-sharing-buttons__services-list.has-large-icon-size{font-size:24px}.jetpack-sharing-buttons__services-list.has-huge-icon-size{font-size:36px}@media print{.jetpack-sharing-buttons__services-list{display:none!important}}.editor-styles-wrapper .wp-block-jetpack-sharing-buttons{gap:0;padding-inline-start:0}ul.jetpack-sharing-buttons__services-list.has-background{padding:1.25em 2.375em} </style> <style id='classic-theme-styles-inline-css' type='text/css'> /*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} </style> <style id='global-styles-inline-css' type='text/css'> :root{--wp--preset--aspect-ratio--square: 1;--wp--preset--aspect-ratio--4-3: 4/3;--wp--preset--aspect-ratio--3-4: 3/4;--wp--preset--aspect-ratio--3-2: 3/2;--wp--preset--aspect-ratio--2-3: 2/3;--wp--preset--aspect-ratio--16-9: 16/9;--wp--preset--aspect-ratio--9-16: 9/16;--wp--preset--color--black: #000000;--wp--preset--color--cyan-bluish-gray: #abb8c3;--wp--preset--color--white: #ffffff;--wp--preset--color--pale-pink: #f78da7;--wp--preset--color--vivid-red: #cf2e2e;--wp--preset--color--luminous-vivid-orange: #ff6900;--wp--preset--color--luminous-vivid-amber: #fcb900;--wp--preset--color--light-green-cyan: #7bdcb5;--wp--preset--color--vivid-green-cyan: #00d084;--wp--preset--color--pale-cyan-blue: #8ed1fc;--wp--preset--color--vivid-cyan-blue: #0693e3;--wp--preset--color--vivid-purple: #9b51e0;--wp--preset--gradient--vivid-cyan-blue-to-vivid-purple: linear-gradient(135deg,rgba(6,147,227,1) 0%,rgb(155,81,224) 100%);--wp--preset--gradient--light-green-cyan-to-vivid-green-cyan: linear-gradient(135deg,rgb(122,220,180) 0%,rgb(0,208,130) 100%);--wp--preset--gradient--luminous-vivid-amber-to-luminous-vivid-orange: linear-gradient(135deg,rgba(252,185,0,1) 0%,rgba(255,105,0,1) 100%);--wp--preset--gradient--luminous-vivid-orange-to-vivid-red: linear-gradient(135deg,rgba(255,105,0,1) 0%,rgb(207,46,46) 100%);--wp--preset--gradient--very-light-gray-to-cyan-bluish-gray: linear-gradient(135deg,rgb(238,238,238) 0%,rgb(169,184,195) 100%);--wp--preset--gradient--cool-to-warm-spectrum: linear-gradient(135deg,rgb(74,234,220) 0%,rgb(151,120,209) 20%,rgb(207,42,186) 40%,rgb(238,44,130) 60%,rgb(251,105,98) 80%,rgb(254,248,76) 100%);--wp--preset--gradient--blush-light-purple: linear-gradient(135deg,rgb(255,206,236) 0%,rgb(152,150,240) 100%);--wp--preset--gradient--blush-bordeaux: linear-gradient(135deg,rgb(254,205,165) 0%,rgb(254,45,45) 50%,rgb(107,0,62) 100%);--wp--preset--gradient--luminous-dusk: linear-gradient(135deg,rgb(255,203,112) 0%,rgb(199,81,192) 50%,rgb(65,88,208) 100%);--wp--preset--gradient--pale-ocean: linear-gradient(135deg,rgb(255,245,203) 0%,rgb(182,227,212) 50%,rgb(51,167,181) 100%);--wp--preset--gradient--electric-grass: linear-gradient(135deg,rgb(202,248,128) 0%,rgb(113,206,126) 100%);--wp--preset--gradient--midnight: linear-gradient(135deg,rgb(2,3,129) 0%,rgb(40,116,252) 100%);--wp--preset--font-size--small: 13px;--wp--preset--font-size--medium: 20px;--wp--preset--font-size--large: 36px;--wp--preset--font-size--x-large: 42px;--wp--preset--spacing--20: 0.44rem;--wp--preset--spacing--30: 0.67rem;--wp--preset--spacing--40: 1rem;--wp--preset--spacing--50: 1.5rem;--wp--preset--spacing--60: 2.25rem;--wp--preset--spacing--70: 3.38rem;--wp--preset--spacing--80: 5.06rem;--wp--preset--shadow--natural: 6px 6px 9px rgba(0, 0, 0, 0.2);--wp--preset--shadow--deep: 12px 12px 50px rgba(0, 0, 0, 0.4);--wp--preset--shadow--sharp: 6px 6px 0px rgba(0, 0, 0, 0.2);--wp--preset--shadow--outlined: 6px 6px 0px -3px rgba(255, 255, 255, 1), 6px 6px rgba(0, 0, 0, 1);--wp--preset--shadow--crisp: 6px 6px 0px rgba(0, 0, 0, 1);}:where(.is-layout-flex){gap: 0.5em;}:where(.is-layout-grid){gap: 0.5em;}body .is-layout-flex{display: flex;}.is-layout-flex{flex-wrap: wrap;align-items: center;}.is-layout-flex > :is(*, div){margin: 0;}body .is-layout-grid{display: grid;}.is-layout-grid > :is(*, div){margin: 0;}:where(.wp-block-columns.is-layout-flex){gap: 2em;}:where(.wp-block-columns.is-layout-grid){gap: 2em;}:where(.wp-block-post-template.is-layout-flex){gap: 1.25em;}:where(.wp-block-post-template.is-layout-grid){gap: 1.25em;}.has-black-color{color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-color{color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-color{color: var(--wp--preset--color--white) !important;}.has-pale-pink-color{color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-color{color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-color{color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-color{color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-color{color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-color{color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-color{color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-color{color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-color{color: var(--wp--preset--color--vivid-purple) !important;}.has-black-background-color{background-color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-background-color{background-color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-background-color{background-color: var(--wp--preset--color--white) !important;}.has-pale-pink-background-color{background-color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-background-color{background-color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-background-color{background-color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-background-color{background-color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-background-color{background-color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-background-color{background-color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-background-color{background-color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-background-color{background-color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-background-color{background-color: var(--wp--preset--color--vivid-purple) !important;}.has-black-border-color{border-color: var(--wp--preset--color--black) !important;}.has-cyan-bluish-gray-border-color{border-color: var(--wp--preset--color--cyan-bluish-gray) !important;}.has-white-border-color{border-color: var(--wp--preset--color--white) !important;}.has-pale-pink-border-color{border-color: var(--wp--preset--color--pale-pink) !important;}.has-vivid-red-border-color{border-color: var(--wp--preset--color--vivid-red) !important;}.has-luminous-vivid-orange-border-color{border-color: var(--wp--preset--color--luminous-vivid-orange) !important;}.has-luminous-vivid-amber-border-color{border-color: var(--wp--preset--color--luminous-vivid-amber) !important;}.has-light-green-cyan-border-color{border-color: var(--wp--preset--color--light-green-cyan) !important;}.has-vivid-green-cyan-border-color{border-color: var(--wp--preset--color--vivid-green-cyan) !important;}.has-pale-cyan-blue-border-color{border-color: var(--wp--preset--color--pale-cyan-blue) !important;}.has-vivid-cyan-blue-border-color{border-color: var(--wp--preset--color--vivid-cyan-blue) !important;}.has-vivid-purple-border-color{border-color: var(--wp--preset--color--vivid-purple) !important;}.has-vivid-cyan-blue-to-vivid-purple-gradient-background{background: var(--wp--preset--gradient--vivid-cyan-blue-to-vivid-purple) !important;}.has-light-green-cyan-to-vivid-green-cyan-gradient-background{background: var(--wp--preset--gradient--light-green-cyan-to-vivid-green-cyan) !important;}.has-luminous-vivid-amber-to-luminous-vivid-orange-gradient-background{background: var(--wp--preset--gradient--luminous-vivid-amber-to-luminous-vivid-orange) !important;}.has-luminous-vivid-orange-to-vivid-red-gradient-background{background: var(--wp--preset--gradient--luminous-vivid-orange-to-vivid-red) !important;}.has-very-light-gray-to-cyan-bluish-gray-gradient-background{background: var(--wp--preset--gradient--very-light-gray-to-cyan-bluish-gray) !important;}.has-cool-to-warm-spectrum-gradient-background{background: var(--wp--preset--gradient--cool-to-warm-spectrum) !important;}.has-blush-light-purple-gradient-background{background: var(--wp--preset--gradient--blush-light-purple) !important;}.has-blush-bordeaux-gradient-background{background: var(--wp--preset--gradient--blush-bordeaux) !important;}.has-luminous-dusk-gradient-background{background: var(--wp--preset--gradient--luminous-dusk) !important;}.has-pale-ocean-gradient-background{background: var(--wp--preset--gradient--pale-ocean) !important;}.has-electric-grass-gradient-background{background: var(--wp--preset--gradient--electric-grass) !important;}.has-midnight-gradient-background{background: var(--wp--preset--gradient--midnight) !important;}.has-small-font-size{font-size: var(--wp--preset--font-size--small) !important;}.has-medium-font-size{font-size: var(--wp--preset--font-size--medium) !important;}.has-large-font-size{font-size: var(--wp--preset--font-size--large) !important;}.has-x-large-font-size{font-size: var(--wp--preset--font-size--x-large) !important;} :where(.wp-block-post-template.is-layout-flex){gap: 1.25em;}:where(.wp-block-post-template.is-layout-grid){gap: 1.25em;} :where(.wp-block-columns.is-layout-flex){gap: 2em;}:where(.wp-block-columns.is-layout-grid){gap: 2em;} :root :where(.wp-block-pullquote){font-size: 1.5em;line-height: 1.6;} </style> <style id='akismet-widget-style-inline-css' type='text/css'> .a-stats { --akismet-color-mid-green: #357b49; --akismet-color-white: #fff; --akismet-color-light-grey: #f6f7f7; max-width: 350px; width: auto; } .a-stats * { all: unset; box-sizing: border-box; } .a-stats strong { font-weight: 600; } .a-stats a.a-stats__link, .a-stats a.a-stats__link:visited, .a-stats a.a-stats__link:active { background: var(--akismet-color-mid-green); border: none; box-shadow: none; border-radius: 8px; color: var(--akismet-color-white); cursor: pointer; display: block; font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', 'Roboto', 'Oxygen-Sans', 'Ubuntu', 'Cantarell', 'Helvetica Neue', sans-serif; font-weight: 500; padding: 12px; text-align: center; text-decoration: none; transition: all 0.2s ease; } /* Extra specificity to deal with TwentyTwentyOne focus style */ .widget .a-stats a.a-stats__link:focus { background: var(--akismet-color-mid-green); color: var(--akismet-color-white); text-decoration: none; } .a-stats a.a-stats__link:hover { filter: brightness(110%); box-shadow: 0 4px 12px rgba(0, 0, 0, 0.06), 0 0 2px rgba(0, 0, 0, 0.16); } .a-stats .count { color: var(--akismet-color-white); display: block; font-size: 1.5em; line-height: 1.4; padding: 0 13px; white-space: nowrap; } </style> <link rel='stylesheet' id='really_simple_share_style-css' href='https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/style.css?ver=6.7.2' type='text/css' media='all' /> <link rel="https://api.w.org/" href="https://scottaaronson.blog/index.php?rest_route=/" /><link rel="EditURI" type="application/rsd+xml" title="RSD" href="https://scottaaronson.blog/xmlrpc.php?rsd" /> <script type="text/javascript"> //<![CDATA[ !function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0];if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src="https://platform.twitter.com/widgets.js";fjs.parentNode.insertBefore(js,fjs);}}(document,"script","twitter-wjs"); window.___gcfg = {lang: "en"}; (function() { var po = document.createElement("script"); po.type = "text/javascript"; po.async = true; po.src = "https://apis.google.com/js/plusone.js"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(po, s); })(); //]]> </script> <style>img#wpstats{display:none}</style> <meta name="description" content="8 posts published by Scott during December 1999" />  <meta property="og:type" content="website" /> <meta property="og:title" content="August 2007 – Shtetl-Optimized" /> <meta property="og:site_name" content="Shtetl-Optimized" /> <meta property="og:image" content="https://149663533.v2.pressablecdn.com/wp-content/uploads/2021/10/cropped-Jacket.gif" /> <meta property="og:image:width" content="512" /> <meta property="og:image:height" content="512" /> <meta property="og:image:alt" content="" /> <meta property="og:locale" content="en_US" />  <link rel="icon" href="https://149663533.v2.pressablecdn.com/wp-content/uploads/2021/10/cropped-Jacket-32x32.gif" sizes="32x32" /> <link rel="icon" href="https://149663533.v2.pressablecdn.com/wp-content/uploads/2021/10/cropped-Jacket-192x192.gif" sizes="192x192" /> <link rel="apple-touch-icon" href="https://149663533.v2.pressablecdn.com/wp-content/uploads/2021/10/cropped-Jacket-180x180.gif" /> <meta name="msapplication-TileImage" content="https://149663533.v2.pressablecdn.com/wp-content/uploads/2021/10/cropped-Jacket-270x270.gif" /> <style type="text/css" id="wp-custom-css"> #content .commentlist>li li{ margin: 0; padding: 0; list-style: disc; } </style> <script> window.addEventListener('DOMContentLoaded', function(){ var typesetLastTimeout = null; var doTypeset = () => { if(typesetLastTimeout) clearTimeout(typesetLastTimeout); typesetLastTimeout = setTimeout(() => MathJax.Hub.Queue(["Typeset",MathJax.Hub,"commentPreview"]), 300); }; document.querySelector("#comment").addEventListener('keydown', doTypeset); }); </script> </head> <body bgcolor="black"> <div id="page"> <div id="header"> <div id="headerimg"> <h1><a href="https://scottaaronson.blog/">Shtetl-Optimized</a></h1> <div class="description">The Blog of Scott Aaronson <br><br><font color="yellow" size="-1">If you take nothing else from this blog: quantum computers won't <br>solve hard problems instantly by just trying all solutions in parallel.</font> <br><blink><a href="https://thezvi.substack.com/p/childhood-and-education-9-school"><font color="white">Also, please read Zvi Mowshowitz's masterpiece on how to fix K-12 education!</font></a></blink></div> </div> </div> <hr /> <div id="content" class="narrowcolumn"> <h2 class="pagetitle">Archive for August, 2007</h2> <div class="navigation"> <div class="alignleft"></div> <div class="alignright"></div> </div> <div class="post"> <h3 id="post-267"><a href="https://scottaaronson.blog/?p=267" rel="bookmark" title="Permanent Link to What’s going down in AarTown">What’s going down in AarTown</a></h3> <small>Friday, August 31st, 2007</small> <div class="entry"> <p>Taking a cue from the <a href="http://dabacon.org/pontiff/?p=1604">Pontiff</a>, I thought I’d provide three quick updates on my personal life (no, not my <em>personal</em> personal life; that’s none of your business).</p> <ol> <li>Last week I bought and moved into a condo in East Cambridge, a 10-minute walk from campus, with lovely views of Boston, the Charles River, and the Red Line T going over the bridge:<center><br /> <a href="https://149663533.v2.pressablecdn.com/apt1.jpg"><img decoding="async" src="https://149663533.v2.pressablecdn.com/apt1sm.jpg" align="middle"></a><a href="https://149663533.v2.pressablecdn.com/apt2.jpg"><img decoding="async" src="https://149663533.v2.pressablecdn.com/apt2sm.jpg"></a></center><br /> (That’s mom on the sofa.) I can’t stress enough how fundamentally my life has changed now that I’m a homeowner. For example, instead of paying rent each month, I now pay something called a “mortgage,” and instead of going to a landlord, it goes to a bank. Also I get a massive tax break for some reason.</li> <li>The students showed up this week, and the semester is here. No, I’m not teaching this fall, but there’s still plenty to do, from organizing a theory lunch to deciding what kind of whiteboard should go in my office. (With a border or without? How big a tray for pens? These are serious decisions.) On Wednesday I went to an orientation for new MIT faculty, at which I got to tell President <a href="http://web.mit.edu/hockfield/biography.html">Susan Hockfield</a> about quantum lower bounds, the prospects for practical quantum computers, and how her fine institution rejected me twice. Along with the usual pleasantries, Hockfield said one thing that deeply impressed me: “I know it’s gone out of fashion in many places, but you’re still allowed to use the word ‘truth’ here.”</li> <li><em>Besides</em> moving, <em>besides</em> getting oriented, I’ve <em>also</em> been distracted from my blogging career by involvement with some … what’s it called? … actual research. Sorry about that; I assure you it’s just a temporary aberration.</li> </ol> <div style="min-height:33px;" class="really_simple_share really_simple_share_button robots-nocontent snap_nopreview"><div class="really_simple_share_facebook_like" style="width:100px;"><div class="fb-like" data-href="https://scottaaronson.blog/?p=267" data-layout="button_count" data-width="100" ></div></div><div class="really_simple_share_twitter" style="width:100px;"><a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-text="What’s going down in AarTown" data-url="https://scottaaronson.blog/?p=267" data-via="" ></a></div><div class="really_simple_share_google1" style="width:80px;"><div class="g-plusone" data-size="medium" data-href="https://scottaaronson.blog/?p=267" ></div></div><div class="really_simple_share_specificfeeds_follow" style="width:110px;"><a href="http://www.specificfeeds.com/follow" target="_blank"><img decoding="async" src="https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/images/specificfeeds_follow.png" alt="Email, RSS" title="Email, RSS" /> Follow</a></div><div class="really_simple_share_facebook_share_new" style="width:110px;"><div class="fb-share-button" data-href="https://scottaaronson.blog/?p=267" data-type="button_count" data-width="110"></div></div></div> <div class="really_simple_share_clearfix"></div> </div> <p class="postmetadata">Posted in <a href="https://scottaaronson.blog/?cat=10" rel="category">Adventures in Meatspace</a>, <a href="https://scottaaronson.blog/?cat=3" rel="category">Procrastination</a> | <a href="https://scottaaronson.blog/?p=267#comments">11 Comments »</a></p> </div> <div class="post"> <h3 id="post-266"><a href="https://scottaaronson.blog/?p=266" rel="bookmark" title="Permanent Link to What Google Won’t Find">What Google Won’t Find</a></h3> <small>Friday, August 31st, 2007</small> <div class="entry"> <p>While I rummage around the brain for something more controversial to blog (that’s nevertheless not <a href="https://scottaaronson.blog/?p=260">too</a> controversial), here, for your reading pleasure, is a talk I gave a couple weeks ago at Google Cambridge. Hardcore <em>Shtetl-Optimized</em> fans will find little here to surprise them, but for new or occasional readers, this is about the clearest statement I’ve written of my religio-ethico-complexity-theoretic beliefs.</p> <p><strong>What Google Won’t Find</strong></p> <p>As I probably mentioned when I spoke at your Mountain View location two years ago, it’s a funny feeling when an entity that knows everything that ever can be known or has been known or will be known invites you to give a talk — what are you supposed to say?</p> <p>Well, I thought I’d talk about “What Google Won’t Find.” In other words, what have we learned over the last 15 years or so about the ultimate physical limits of search — whether it’s search of a physical database like Google’s, or of the more abstract space of solutions to a combinatorial problem?</p> <p>On the spectrum of computer science, I’m about as theoretical as you can get. One way to put it is that I got through CS grad school at Berkeley without really learning any programming language other than QBASIC. So it might surprise you that earlier this year, I was spending much of my time talking to <em>business</em> reporters. Why? Because there was this company near Vancouver called D-Wave Systems, which was announcing to the press that it had built the world’s first commercial quantum computer.</p> <p>Let’s ignore the “commercial” part, because I don’t really understand economics — these days, you can apparently make billions of dollars giving away some service for free! Let’s instead focus on the question: did D-Wave <em>actually</em> build a quantum computer? Well, they apparently built a device with 16 very noisy superconducting quantum bits (or qubits), which they say they’ve used to help solve extremely small Sudoku puzzles.</p> <p>The trouble is, we’ve known for years that if qubits are sufficiently noisy — if they leak a sufficient amount of information into their environment — then they behave essentially like classical bits. Furthermore, D-Wave has refused to answer extremely basic technical questions about how high their noise rates are and so forth — they care about serving their customers, not answering nosy questions from academics. (Recently D-Wave founder Geordie Rose <a href="http://www.walrusmagazine.ca/articles/2007.08.10-quantum-conundrum/#155">offered</a> to answer my questions if I was interested in buying one of his machines. I replied that I <em>was</em> interested — my offer was $10 US — and I now await his answers as a prospective customer.)</p> <p>To make a long story short, it’s consistent with the evidence that what D-Wave actually built would best be described as a 16-bit <em>classical</em> computer. I don’t mean 16 bits in terms of the architecture; I mean sixteen actual bits. And there’s some prior art for that.</p> <p>But that’s actually not what annoyed me the most about the D-Wave announcement. What annoyed me were all the articles in the popular press — including places as reputable as <em>The Economist</em> — that said, what D-Wave has built is a machine that can try every possible solution in parallel and instantly pick the right one. This is what a quantum computer is; this is how it works.</p> <p>It’s amazing to me how, as soon as the word “quantum” is mentioned, all the ordinary rules of journalism go out the window. No one thinks to ask: is that <em>really</em> what a quantum computer could do?</p> <p>It turns out that, even though we don’t yet have scalable quantum computers, we do know something about what they could do if we <em>did</em> have them.</p> <p>A quantum computer is a device that would exploit the laws of quantum mechanics to solve certain computational problems asymptotically faster than we know how to solve them with any computer today. Quantum mechanics — which has been our basic framework for physics for the last 80 years — is a theory that’s like probability theory, except that instead of real numbers called probabilities, you now have complex numbers called amplitudes. And the interesting thing about these complex numbers is that they can “interfere” with each other: they can cancel each other out.</p> <p>In particular, to find the probability of something happening, you have to add the amplitudes for all the possible ways it <em>could</em> have happened, and then take the square of the absolute value of the result. And if some of the ways an event could happen have positive amplitude and others have negative amplitude, then the amplitudes can cancel out, so that the event <em>doesn’t happen at all</em>. This is exactly what’s going on in the famous double-slit experiment: at certain spots on a screen, the different paths a photon could’ve taken to get to that spot interfere destructively and cancel each other out, and as a result no photon is seen.</p> <p>Now, the idea of quantum computing is to set up a <em>massive</em> double-slit experiment with exponentially many paths — and to try to arrange things so that the paths leading to wrong answers interfere destructively and cancel each other out, while the paths leading to right answers interfere <em>constructively</em> and are therefore observed with high probability.</p> <p>You can see it’s a subtle effect that we’re aiming for. And indeed, it’s only for a few specific problems that people have figured out how to choreograph an interference pattern to solve the problem efficiently — that is, in polynomial time.</p> <p>One of these problems happens to be that of factoring integers. Thirteen years ago, Peter Shor discovered that a quantum computer could efficient apply Fourier transforms over exponentially-large abelian groups, and thereby find the periods of exponentially-long periodic sequences, and thereby factor integers, and thereby break the RSA cryptosystem, and thereby snarf people’s credit card numbers. So that’s one application of quantum computers.</p> <p>On the other hand — and this is the most common misconception about quantum computing I’ve encountered — we do not, repeat <strong>do not</strong>, know a quantum algorithm to solve NP-complete problems in polynomial time. For “generic” problems of finding a needle in a haystack, most of us believe that quantum computers will give at most a polynomial advantage over classical ones.</p> <p>At this point I should step back. How many of you have heard of the following question: <strong>Does P=NP?</strong></p> <p>Yeah, this is a problem so profound that it’s appeared on at least two TV shows (<em>The Simpsons</em> and <em>NUMB3RS</em>). It’s also one of the seven (now six) problems for which the Clay Math Institute is offerring a million-dollar prize for a solution.</p> <p>Apparently the mathematicians had to debate whether P vs. NP was “deep” enough to include in their list. Personally, I take it as obvious that it’s the deepest of them all. And the reason is this: if you had a fast algorithm for solving NP-complete problems, then not only could you solve P vs. NP, <em>you could presumably also solve the other six problems</em>. You’d simply program your computer to search through all possible proofs of at most (say) a billion symbols, in some formal system like Zermelo-Fraenkel set theory. If such a proof existed, you’d find it in a reasonable amount of time. (And if the proof had more than a billion symbols, it’s not clear you’d even want to see it!)</p> <p>This raises an important point: many people — even computer scientists — don’t appreciate just how profound the consequences would be if P=NP. They think it’s about scheduling airline flights better, or packing more boxes in your truck. Of course, it <em>is</em> about those things — but the point is that you can have a set of boxes such that <em>if</em> you could pack them into your truck, then you would also have proved the Riemann Hypothesis!</p> <p>Of course, while the proof eludes us, we believe that P鈮燦P. We believe there’s no algorithm to solve NP-complete problems in deterministic polynomial time. But personally, I would actually make a stronger conjecture:</p> <blockquote><p><strong>There is <em>no</em> physical means to solve NP-complete problems in polynomial time — not with classical computers, not with quantum computers, not with anything else.</strong></p></blockquote> <p>You could call this the “No SuperSearch Principle.” It says that, if you’re going to find a needle in a haystack, then you’ve got to expend at least <em>some</em> computational effort sifting through the hay.</p> <p>I see this principle as analogous to the Second Law of Thermodynamics or the impossibility of superluminal signalling. That is, it’s a technological limitation which is <em>also</em> a pretty fundamental fact about the laws of physics. Like those other principles, it could always be falsified by experiment, but after a while it seems manifestly more useful to <em>assume</em> it’s true and then see what the consequences are for other things.</p> <p>OK, so what do we actually <em>know</em> about the ability of quantum computers to solve NP-complete problems efficiently? Well, of course we can’t <em>prove</em> it’s impossible, since we can’t even prove it’s impossible for classical computers — that’s the P vs. NP problem! We might hope to at least prove that quantum computers can’t solve NP-complete problems in polynomial time <em>unless classical computers can also</em> — but even that, alas, seems far beyond our ability to prove.</p> <p>What we <em>can</em> prove is this: suppose you throw away the structure of an NP-complete problem, and just consider it as an abstract, featureless space of 2<sup>n</sup> possible solutions, where the only thing you can do is guess a solution and check whether it’s right or not. In that case it’s obvious that a classical computer will need ~2<sup>n</sup> steps to find a solution. But what if you used a quantum computer, which could “guess” all possible solutions in superposition? Well, even then, you’d still need at least ~2<sup>n/2</sup> steps to find a solution. This is called the BBBV Theorem, and was one of the first things learned about the power of quantum computers.</p> <p>Intuitively, even though a quantum computer in some sense involves exponentially many paths or “parallel universes,” the single universe that happened on the answer can’t shout above all the other universes: “hey, over here!” It can only gradually make the others aware of its presence.</p> <p>As it turns out, the 2<sup>n/2</sup> bound is actually achievable. For in 1996, Lov Grover showed that a quantum computer <em>can</em> search a list of N items using only 鈭歂 steps. It seems to me that this result should clearly feature in Google’s business plan.</p> <p>Of course in real life, NP-complete problems <em>do</em> have structure, and algorithms like local search and backtrack search exploit that structure. Because of this, the BBBV theorem can’t <em>rule out</em> a fast quantum algorithm for NP-complete problems. It merely shows that, <em>if</em> such an algorithm existed, then it couldn’t work the way 99% of everyone who’s ever heard of quantum computing thinks it would!</p> <p>You might wonder whether there’s any proposal for a quantum algorithm that <em>would</em> exploit the structure of NP-complete problems. As it turns out, there’s one such proposal: the “quantum adiabatic algorithm” of Farhi et al., which can be seen as the quantum version of simulated annealing. Intriguingly, Farhi and his collaborators proved that, on <em>some</em> problem instances where classical simulated annealing would take exponential time, the quantum adiabatic algorithm takes only polynomial time. Alas, we <em>also</em> know of problem instances where the adiabatic algorithm takes exponential time just as simulated annealing does. So while this is still an active research area, right now the adiabatic algorithm does <em>not</em> look like a magic bullet for solving NP-complete problems.</p> <p>If quantum computers can’t solve NP-complete problems in polynomial time, it raises an extremely interesting question: is there <em>any</em> physical means to solve NP-complete problems in polynomial time?</p> <p>Well, there have been lots of proposals. One of my favorites involves taking two glass plates with pegs between them, and dipping the resulting contraption into a tub of soapy water. The idea is that the soap bubbles that form between the pegs should trace out the minimum Steiner tree — that is, the minimum total length of line segments connecting the pegs, where the segments can meet at points other than the pegs themselves. Now, this is known to be an NP-hard optimization problem. So, it looks like Nature is solving NP-hard problems in polynomial time!</p> <p>You might say there’s an obvious difficulty: the soap bubbles could get trapped in a local optimum that’s different from the global optimum. By analogy, a rock in a mountain crevice could reach a lower state of potential energy by rolling up first and then down … but is rarely observed to do so!</p> <p>And if you said that, you’d be absolutely right. But that didn’t stop two guys a few years ago from writing a <a href="http://www.arxiv.org/abs/cs/0406056">paper</a> in which they claimed, not only that soap bubbles solve NP-complete problems in polynomial time, but that that fact proves P=NP! In debates about this paper on newsgroups, several posters raised the duh-obvious point that soap bubbles can get trapped at local optima. But then another poster opined that that’s just an academic “party line,” and that he’d be willing to bet that no one had actually done an experiment to prove it.</p> <p>Long story short, I went to the hardware store, bought some <a href="http://www.scottaaronson.com/soapbubble.jpg">glass plates</a>, liquid soap, etc., and found that, while Nature <em>does</em> often find a minimum Steiner tree with 4 or 5 pegs, it tends to get stuck at local optima with larger numbers of pegs. Indeed, often the soap bubbles settle down to a configuration which is not even a tree (i.e. contains “cycles of soap”), and thus provably can’t be optimal.</p> <p>The situation is similar for protein folding. Again, people have said that Nature seems to be solving an NP-hard optimization problem in every cell of your body, by letting the proteins fold into their minimum-energy configurations. But there are two problems with this claim. The first problem is that proteins, just like soap bubbles, sometimes get stuck in suboptimal configurations — indeed, it’s believed that’s exactly what happens with Mad Cow Disease. The second problem is that, to the extent that proteins <em>do</em> usually fold into their optimal configurations, there’s an obvious reason why they would: natural selection! If there were a protein that could only be folded by proving the Riemann Hypothesis, the gene that coded for it would quickly get weeded out of the gene pool.</p> <p>So: quantum computers, soap bubbles, proteins … if we want to solve NP-complete problems in polynomial time in the physical world, what’s left? Well, we can try going to more exotic physics. For example, since we don’t yet have a quantum theory of gravity, people have felt free to speculate that if we <em>did</em> have one, it would give us an efficient way to solve NP-complete problems. For example, maybe the theory would allow closed timelike curves, which would let us solve NP-complete and even harder problems by (in some sense) sending the answer back in time to before we started.</p> <p>In my view, though, it’s more likely that a quantum theory of gravity will do the exact opposite: that is, it will <em>limit</em> our computational powers, relative to what they would’ve been in a universe without gravity. To see why, consider one of the oldest “extravagant” computing proposals: the Zeno computer. This is a computer that runs the first step of a program in one second, the second step in half a second, the third step in a quarter second, the fourth step in an eighth second, and so on, so that after two seconds it’s run infinitely many steps. (It reminds me of the old joke about the supercomputer that was so fast, it could do an infinite loop in 2.5 seconds.)</p> <blockquote><p><strong>Question from the floor:</strong> In what sense is this even a “proposal”?</p> <p><strong>Answer:</strong> Well, it’s a proposal in the sense that people actually write papers about it! (Google “<a href="http://www.google.com/search?q=hypercomputation">hypercomputation</a>.”) Whether they <em>should</em> be writing those papers a separate question…</p></blockquote> <p>Now, the Zeno computer strikes most computer scientists — me included — as a joke. But <em>why</em> is it a joke? Can we say anything better than that it feels absurd to us?</p> <p>As it turns out, this question takes us straight into some of the frontier issues in theoretical physics. In particular, one of the few things physicists think they know about quantum gravity — one of the few things both the string theorists and their critics largely agree on — is that, at the so-called “Planck scale” of about 10<sup>-33</sup> centimeters or 10<sup>-43</sup> seconds, our usual notions of space and time are going to break down. As one manifestation of this, if you tried to build a clock that ticked more than about 10<sup>43</sup> times per second, that clock would use so much energy that it would collapse to a black hole. Ditto for a computer that performed more than about 10<sup>43</sup> operations per second, or for a hard disk that stored more than about 10<sup>69</sup> bits per square meter of surface area. (Together with the finiteness of the speed of light and the exponential expansion of the universe, this implies that, contrary to what you might have thought, there <em>is</em> a fundamental physical limit on how much disk space Gmail will ever be able to offer its subscribers…)</p> <p>To summarize: while I believe what I called the “No SuperSearch Principle” — that is, while I believe there are fundamental physical limits to efficient computer search — I hope I’ve convinced you that understanding <em>why </em>these limits exist takes us straight into some of the deepest issues in math and physics. To me that’s so much the better — since it suggests that not only are the limits <em>correct</em>, but (more importantly) they’re also nontrivial.</p> <p>Thank you.</p> <p><input id="gwProxy" type="hidden" /><input onclick="jsCall();" id="jsProxy" type="hidden" /></p> <div style="min-height:33px;" class="really_simple_share really_simple_share_button robots-nocontent snap_nopreview"><div class="really_simple_share_facebook_like" style="width:100px;"><div class="fb-like" data-href="https://scottaaronson.blog/?p=266" data-layout="button_count" data-width="100" ></div></div><div class="really_simple_share_twitter" style="width:100px;"><a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-text="What Google Won’t Find" data-url="https://scottaaronson.blog/?p=266" data-via="" ></a></div><div class="really_simple_share_google1" style="width:80px;"><div class="g-plusone" data-size="medium" data-href="https://scottaaronson.blog/?p=266" ></div></div><div class="really_simple_share_specificfeeds_follow" style="width:110px;"><a href="http://www.specificfeeds.com/follow" target="_blank"><img decoding="async" src="https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/images/specificfeeds_follow.png" alt="Email, RSS" title="Email, RSS" /> Follow</a></div><div class="really_simple_share_facebook_share_new" style="width:110px;"><div class="fb-share-button" data-href="https://scottaaronson.blog/?p=266" data-type="button_count" data-width="110"></div></div></div> <div class="really_simple_share_clearfix"></div> </div> <p class="postmetadata">Posted in <a href="https://scottaaronson.blog/?cat=5" rel="category">Complexity</a>, <a href="https://scottaaronson.blog/?cat=30" rel="category">Mirrored on CSAIL Blog</a>, <a href="https://scottaaronson.blog/?cat=4" rel="category">Quantum</a>, <a href="https://scottaaronson.blog/?cat=17" rel="category">Speaking Truth to Parallelism</a> | <a href="https://scottaaronson.blog/?p=266#comments">60 Comments »</a></p> </div> <div class="post"> <h3 id="post-265"><a href="https://scottaaronson.blog/?p=265" rel="bookmark" title="Permanent Link to Does it come with a 14-Gyr warranty?">Does it come with a 14-Gyr warranty?</a></h3> <small>Sunday, August 19th, 2007</small> <div class="entry"> <p>As many of you probably saw, John Tierney of the <em>New York Times</em> <a href="http://www.nytimes.com/2007/08/14/science/14tier.html?_r=1&oref=slogin">thinks</a> there’s a ~50% chance we’re living in a computer simulation, having been persuaded by Nick Bostrom’s infamous <a href="http://www.simulation-argument.com/">simulation argument</a>.</p> <p>(This argument, incidentally, is something that occurred to me as a teenager, and I’m guessing to many others of nerdly leanings as well. I didn’t consider it a profound metaphysical discovery, just a sign I needed to get out more.)</p> <p>Peter Woit <a href="http://www.math.columbia.edu/~woit/wordpress/?p=586">feels strongly</a> that debates about whether the universe is a computer are not science and therefore have no place in the <em>Times</em> science section. Robin Hanson <a href="http://www.typepad.com/t/comments?__mode=red&user_id=475590&id=79926417">retorts</a> that “rather than complain that something is not ‘science,’ or not ‘philosophy,’ it is much better to just say more specifically what it is that you don’t like about it.” Peter Shor <a href="http://www.math.columbia.edu/~woit/wordpress/?p=583#comment-27448">points out</a> that if we’re living in a simulation, then the incompatibility of quantum mechanics with general relativity might simply be a bug, in which case the universe will crash when the first black hole evaporates.</p> <p>As for me, I tend to side with Woody Allen: yes, the universe might be a simulation, but where else can you get a decent steak?</p> <p>The last word, however, goes to <a href="http://en.wikipedia.org/wiki/Bender_(Futurama)">Bender Bending Rodriguez</a> of <em>Futurama</em>.</p> <blockquote><p><strong>Bender:</strong> “If that stuff wasn’t real, how can I be sure anything is real? Is it not possible, nay, probable that my whole life is just a product of my or someone else’s imagination?”</p> <p><strong>Clerk:</strong> “No, get out. Next!”</p></blockquote> <p>(<a href="http://www.gotfuturama.com/Multimedia/EpisodeSounds/4ACV14/13.mp3">Click here</a> for the audio clip.)</p> <p><input id="gwProxy" type="hidden" /><input onclick="jsCall();" id="jsProxy" type="hidden" /></p> <div style="min-height:33px;" class="really_simple_share really_simple_share_button robots-nocontent snap_nopreview"><div class="really_simple_share_facebook_like" style="width:100px;"><div class="fb-like" data-href="https://scottaaronson.blog/?p=265" data-layout="button_count" data-width="100" ></div></div><div class="really_simple_share_twitter" style="width:100px;"><a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-text="Does it come with a 14-Gyr warranty?" data-url="https://scottaaronson.blog/?p=265" data-via="" ></a></div><div class="really_simple_share_google1" style="width:80px;"><div class="g-plusone" data-size="medium" data-href="https://scottaaronson.blog/?p=265" ></div></div><div class="really_simple_share_specificfeeds_follow" style="width:110px;"><a href="http://www.specificfeeds.com/follow" target="_blank"><img decoding="async" src="https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/images/specificfeeds_follow.png" alt="Email, RSS" title="Email, RSS" /> Follow</a></div><div class="really_simple_share_facebook_share_new" style="width:110px;"><div class="fb-share-button" data-href="https://scottaaronson.blog/?p=265" data-type="button_count" data-width="110"></div></div></div> <div class="really_simple_share_clearfix"></div> </div> <p class="postmetadata">Posted in <a href="https://scottaaronson.blog/?cat=12" rel="category">Metaphysical Spouting</a>, <a href="https://scottaaronson.blog/?cat=30" rel="category">Mirrored on CSAIL Blog</a> | <a href="https://scottaaronson.blog/?p=265#comments">97 Comments »</a></p> </div> <div class="post"> <h3 id="post-264"><a href="https://scottaaronson.blog/?p=264" rel="bookmark" title="Permanent Link to Toads, lower bounds vie for control of Australia">Toads, lower bounds vie for control of Australia</a></h3> <small>Saturday, August 18th, 2007</small> <div class="entry"> <p>What better way to procrastinate than to <a href="http://www.abc.net.au/rn/scienceshow/stories/2007/2007888.htm">hear an Australian radio show</a> interview me about the quantum query complexity of the collision problem, public-key cryptography, interactive proofs, computational intractability as a law of physics, and my great love for my high school? The first part of the program is about Australia’s population of cane toads (or rather, “tie-oads”). Then at 32:40, they start in with a report on the <a href="https://scottaaronson.blog/?p=258">FQXi conference in Iceland</a>, and interviews with Max Tegmark, Fred Adams, and Simon Saunders. I’m from 39:10 to 46:50.</p> <p>A few comments/corrections:</p> <ul> <li>The interviewer, Pauline Newman, asks me about the practical implications of the collision lower bound, and then cuts to me talking about how quantum computers could break the RSA cryptosystem. Of course, the connection is only an indirect one (the collision lower bound is what gives hope that one could design collision-resistant hash functions that, unlike RSA, are secure even against quantum attacks).</li> </ul> <ul> <li>I said that, when trying to solve jigsaw puzzles or schedule airline flights, there doesn’t seem to be anything one can do that’s fundamentally better than trying every possibility. I should have added, “in the worst case.”</li> </ul> <ul> <li>The reason I mentioned how old I was when IP=PSPACE was proved is not that I’m a narcissist (though I am), but because in a section that was cut, Pauline asked me if <em>I</em> proved IP=PSPACE, and I was trying to make it clear that I didn’t. The theorem was proved by Shamir, building on work of Lund, Fortnow, Karloff, and Nisan.</li> </ul> <ul> <li>Pauline’s assertion that I “took off on a snowmobile without [my] passenger” and “left a distinguished physicist stranded on a glacier” is a gross exaggeration. What happened was, I waited and waited for someone — anyone — to climb onto my snowmobile. When no one did (maybe because everyone was scared by my abysmal driving ability), I figured I should just go.</li> </ul> <p>Anyway, at least the um’s and uh’s seem to have been under control, compared to my <a href="https://scottaaronson.blog/?p=38">interview with Lance</a> two years ago.</p> <div style="min-height:33px;" class="really_simple_share really_simple_share_button robots-nocontent snap_nopreview"><div class="really_simple_share_facebook_like" style="width:100px;"><div class="fb-like" data-href="https://scottaaronson.blog/?p=264" data-layout="button_count" data-width="100" ></div></div><div class="really_simple_share_twitter" style="width:100px;"><a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-text="Toads, lower bounds vie for control of Australia" data-url="https://scottaaronson.blog/?p=264" data-via="" ></a></div><div class="really_simple_share_google1" style="width:80px;"><div class="g-plusone" data-size="medium" data-href="https://scottaaronson.blog/?p=264" ></div></div><div class="really_simple_share_specificfeeds_follow" style="width:110px;"><a href="http://www.specificfeeds.com/follow" target="_blank"><img decoding="async" src="https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/images/specificfeeds_follow.png" alt="Email, RSS" title="Email, RSS" /> Follow</a></div><div class="really_simple_share_facebook_share_new" style="width:110px;"><div class="fb-share-button" data-href="https://scottaaronson.blog/?p=264" data-type="button_count" data-width="110"></div></div></div> <div class="really_simple_share_clearfix"></div> </div> <p class="postmetadata">Posted in <a href="https://scottaaronson.blog/?cat=10" rel="category">Adventures in Meatspace</a>, <a href="https://scottaaronson.blog/?cat=5" rel="category">Complexity</a>, <a href="https://scottaaronson.blog/?cat=4" rel="category">Quantum</a>, <a href="https://scottaaronson.blog/?cat=17" rel="category">Speaking Truth to Parallelism</a> | <a href="https://scottaaronson.blog/?p=264#comments">7 Comments »</a></p> </div> <div class="post"> <h3 id="post-263"><a href="https://scottaaronson.blog/?p=263" rel="bookmark" title="Permanent Link to My Favorite Growth Rates">My Favorite Growth Rates</a></h3> <small>Sunday, August 12th, 2007</small> <div class="entry"> <p><img decoding="async" src="https://149663533.v2.pressablecdn.com/growthrates.gif"></p> <p><strong><span style="color: red;">Update (8/17):</span></strong> Believe it or not, this blog <a href="#comment-13862">actually led to something</a> (scroll down to comment #52 if the link doesn’t work).</p> <div style="min-height:33px;" class="really_simple_share really_simple_share_button robots-nocontent snap_nopreview"><div class="really_simple_share_facebook_like" style="width:100px;"><div class="fb-like" data-href="https://scottaaronson.blog/?p=263" data-layout="button_count" data-width="100" ></div></div><div class="really_simple_share_twitter" style="width:100px;"><a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-text="My Favorite Growth Rates" data-url="https://scottaaronson.blog/?p=263" data-via="" ></a></div><div class="really_simple_share_google1" style="width:80px;"><div class="g-plusone" data-size="medium" data-href="https://scottaaronson.blog/?p=263" ></div></div><div class="really_simple_share_specificfeeds_follow" style="width:110px;"><a href="http://www.specificfeeds.com/follow" target="_blank"><img decoding="async" src="https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/images/specificfeeds_follow.png" alt="Email, RSS" title="Email, RSS" /> Follow</a></div><div class="really_simple_share_facebook_share_new" style="width:110px;"><div class="fb-share-button" data-href="https://scottaaronson.blog/?p=263" data-type="button_count" data-width="110"></div></div></div> <div class="really_simple_share_clearfix"></div> </div> <p class="postmetadata">Posted in <a href="https://scottaaronson.blog/?cat=5" rel="category">Complexity</a>, <a href="https://scottaaronson.blog/?cat=30" rel="category">Mirrored on CSAIL Blog</a>, <a href="https://scottaaronson.blog/?cat=3" rel="category">Procrastination</a> | <a href="https://scottaaronson.blog/?p=263#comments">105 Comments »</a></p> </div> <div class="post"> <h3 id="post-262"><a href="https://scottaaronson.blog/?p=262" rel="bookmark" title="Permanent Link to Death to Verizon">Death to Verizon</a></h3> <small>Saturday, August 11th, 2007</small> <div class="entry"> <p>Needing a token of my years in Waterloo, I figured it was finally time to trade in my Pleistocene Nokia phone for a BlackBerry. So I used some of my startup funds to buy a BlackBerry 8830 World Edition from Verizon. What particularly excited me about this model was that it was advertised as having a built-in GPS receiver — meaning (or so I thought) that I’d be able to pull up Google Maps wherever I was, and never get lost again.</p> <p>Well, today the phone arrived, and I found out that <em>Verizon has disabled the GPS</em> (see <a href="http://www.rimarkable.com/archives/1434">here</a>, <a href="http://forums.crackberry.com/f61/rim-says-8830-gps-autonomous-1921/">here</a>, and <a href="http://www.associatedcontent.com/article/327280/verizon_wireless_pulls_plug_on_blackberry.html">here</a>). The reason, apparently, is that at some unknown time in the future, it plans to sell an inferior navigation service for $10/month, and doesn’t want people getting for free what it will later rip them off for.</p> <p>I’ve been having fun imagining the conversation between Mike Lazaridis (the founder of Research in Motion, the Waterloo-based company that makes BlackBerries) and Verizon:</p> <blockquote><p><strong>Lazaridis:</strong> It’s an abomination! As long as I draw breath, I’ll never agree to your crippling my invention!</p> <p><strong>Verizon CEO (breathing heavily):</strong> Young Lazaridis, come over to the Dark Side.</p> <p><strong>Lazaridis (pause):</strong> Actually, how much are you offering? I’ve been needing cash, ever since blowing all those millions on the Perimeter Institute and the Institute for Quantum Computing…</p></blockquote> <p>Some will say I’m a sucker, buyer beware, etc. The more sympathetic will call me a victim of false advertising — indeed, of the exact sort of corporate behavior that my best friend <a href="http://www.cs.princeton.edu/~jhalderm">Alex Halderman</a> and his adviser <a href="http://www.freedom-to-tinker.com/">Ed Felten</a> have battled for years with some spectacular successes.</p> <p>Recently I attended a talk by the legendary free-software activist <a href="http://en.wikipedia.org/wiki/Richard_Stallman">Richard Stallman</a>, who thundered like an Old Testament prophet about human beings’ inalienable right to understand, modify, and share the technology they own. At the time I agreed with Stallman intellectually but found him a bit obsessive. Now I have my own dog in this fight.</p> <p>I’ve always known that American cell phone companies are evil: they have shitty, unreliable networks, enormous advertising budgets, and miniscule R&D budgets. But Verizon has taken things to a level even I wouldn’t have predicted.</p> <p>We’re not living in anything close to the efficient market dreamed of by my economist friends like <a href="http://hanson.gmu.edu/home.html">Robin Hanson</a>. The invisible hand has palsy and four missing fingers. And the proof is that, when a company like Verizon pulls a Monty Burns, there’s almost no risk it runs — almost nothing it fears. Indeed, about the only risk it <em>does</em> run is that some of its customers might have blogs — and that some of the savvier readers of those blogs might figure out how to hack the crippled phones and share that information with the world…</p> <div style="min-height:33px;" class="really_simple_share really_simple_share_button robots-nocontent snap_nopreview"><div class="really_simple_share_facebook_like" style="width:100px;"><div class="fb-like" data-href="https://scottaaronson.blog/?p=262" data-layout="button_count" data-width="100" ></div></div><div class="really_simple_share_twitter" style="width:100px;"><a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-text="Death to Verizon" data-url="https://scottaaronson.blog/?p=262" data-via="" ></a></div><div class="really_simple_share_google1" style="width:80px;"><div class="g-plusone" data-size="medium" data-href="https://scottaaronson.blog/?p=262" ></div></div><div class="really_simple_share_specificfeeds_follow" style="width:110px;"><a href="http://www.specificfeeds.com/follow" target="_blank"><img decoding="async" src="https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/images/specificfeeds_follow.png" alt="Email, RSS" title="Email, RSS" /> Follow</a></div><div class="really_simple_share_facebook_share_new" style="width:110px;"><div class="fb-share-button" data-href="https://scottaaronson.blog/?p=262" data-type="button_count" data-width="110"></div></div></div> <div class="really_simple_share_clearfix"></div> </div> <p class="postmetadata">Posted in <a href="https://scottaaronson.blog/?cat=16" rel="category">Rage Against Doofosity</a> | <a href="https://scottaaronson.blog/?p=262#comments">42 Comments »</a></p> </div> <div class="post"> <h3 id="post-261"><a href="https://scottaaronson.blog/?p=261" rel="bookmark" title="Permanent Link to Intellectual whack-a-mole">Intellectual whack-a-mole</a></h3> <small>Thursday, August 9th, 2007</small> <div class="entry"> <p>Several readers have now written to me independently, asking for my reaction to the following paper:</p> <blockquote><p><a href="http://www.opticsexpress.org/abstract.cfm?id=140598">An Optical Solution For The Traveling Salesman Problem</a><br /> Tobias Haist and Wolfgang Osten</p> <p>Abstract: We introduce an optical method based on white light interferometry in order to solve the well-known NP鈥揷omplete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non鈥損olynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to N<sup>N</sup> for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal鈥搕o鈥搉oise ratio. The proposed method is meant purely as a gedankenexperiment.</p></blockquote> <p>Look, this is <em>really</em> not hard. You <em>really</em> don’t need a world CompuCrackpotism expert to tell you what to think of this. If you read carefully, the authors were actually kind enough to explain themselves, right in the abstract, why their proposal doesn’t scale. (This, of course, is entirely to their credit, and puts them above ~98% of their colleagues in the burgeoning intersection of computer science, physics, and non-correctness.)</p> <p><font size="-1"><em>Hint:</em> If the number of photons scales exponentially with N, and the photons have high enough energies that you can detect them, then the energy also scales exponentially with N. So by the Schwarzschild bound, the volume also scales exponentially with N; therefore, by locality, so does the time.</font></p> <p><input id="gwProxy" type="hidden" /><input onclick="jsCall();" id="jsProxy" type="hidden" /></p> <div style="min-height:33px;" class="really_simple_share really_simple_share_button robots-nocontent snap_nopreview"><div class="really_simple_share_facebook_like" style="width:100px;"><div class="fb-like" data-href="https://scottaaronson.blog/?p=261" data-layout="button_count" data-width="100" ></div></div><div class="really_simple_share_twitter" style="width:100px;"><a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-text="Intellectual whack-a-mole" data-url="https://scottaaronson.blog/?p=261" data-via="" ></a></div><div class="really_simple_share_google1" style="width:80px;"><div class="g-plusone" data-size="medium" data-href="https://scottaaronson.blog/?p=261" ></div></div><div class="really_simple_share_specificfeeds_follow" style="width:110px;"><a href="http://www.specificfeeds.com/follow" target="_blank"><img decoding="async" src="https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/images/specificfeeds_follow.png" alt="Email, RSS" title="Email, RSS" /> Follow</a></div><div class="really_simple_share_facebook_share_new" style="width:110px;"><div class="fb-share-button" data-href="https://scottaaronson.blog/?p=261" data-type="button_count" data-width="110"></div></div></div> <div class="really_simple_share_clearfix"></div> </div> <p class="postmetadata">Posted in <a href="https://scottaaronson.blog/?cat=5" rel="category">Complexity</a>, <a href="https://scottaaronson.blog/?cat=30" rel="category">Mirrored on CSAIL Blog</a>, <a href="https://scottaaronson.blog/?cat=17" rel="category">Speaking Truth to Parallelism</a> | <a href="https://scottaaronson.blog/?p=261#comments">39 Comments »</a></p> </div> <div class="post"> <h3 id="post-259"><a href="https://scottaaronson.blog/?p=259" rel="bookmark" title="Permanent Link to German comedy">German comedy</a></h3> <small>Sunday, August 5th, 2007</small> <div class="entry"> <p>I know I’ve been a derelict blogger since moving to MIT, allowing far, far too many of you to concentrate on work. But today I’m back with some <em>quality</em> procrastination material.</p> <p>My colleague (and sometime 眉berliberal commenter on this blog) Aram Harrow points me to a <a href="http://www.youtube.com/watch?v=Sdjt6Bl5qdY">safety video for German forklift-truck drivers</a>, which was posted to YouTube with English subtitles. As Aram says, it starts slow but is <em>definitely</em> worth watching to the end.</p> <p>It’s funny: just this weekend, I was volunteering with the Cornell Alumni Association at the Greater Boston Food Bank. My job was to unload 40-pound boxes of canned goods from a forklift truck and place them on a conveyor belt. (And no, this is not something I’d normally do. Normally I’d offer to write a check to pay for ten people stronger than I am to unload boxes for the needy. Long story short, I was invited to do this by an individual of female persuasion.)</p> <p>The whole time I was unloading boxes, I too was a bit worried about forklift safety — but, as I now know, not <em>nearly</em> as worried as I should have been.</p> <div style="min-height:33px;" class="really_simple_share really_simple_share_button robots-nocontent snap_nopreview"><div class="really_simple_share_facebook_like" style="width:100px;"><div class="fb-like" data-href="https://scottaaronson.blog/?p=259" data-layout="button_count" data-width="100" ></div></div><div class="really_simple_share_twitter" style="width:100px;"><a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-text="German comedy" data-url="https://scottaaronson.blog/?p=259" data-via="" ></a></div><div class="really_simple_share_google1" style="width:80px;"><div class="g-plusone" data-size="medium" data-href="https://scottaaronson.blog/?p=259" ></div></div><div class="really_simple_share_specificfeeds_follow" style="width:110px;"><a href="http://www.specificfeeds.com/follow" target="_blank"><img decoding="async" src="https://149663533.v2.pressablecdn.com/wp-content/plugins/really-simple-facebook-twitter-share-buttons/images/specificfeeds_follow.png" alt="Email, RSS" title="Email, RSS" /> Follow</a></div><div class="really_simple_share_facebook_share_new" style="width:110px;"><div class="fb-share-button" data-href="https://scottaaronson.blog/?p=259" data-type="button_count" data-width="110"></div></div></div> <div class="really_simple_share_clearfix"></div> </div> <p class="postmetadata">Posted in <a href="https://scottaaronson.blog/?cat=10" rel="category">Adventures in Meatspace</a>, <a href="https://scottaaronson.blog/?cat=3" rel="category">Procrastination</a> | <a href="https://scottaaronson.blog/?p=259#comments">9 Comments »</a></p> </div> <div class="navigation"> <div class="alignleft"></div> <div class="alignright"></div> </div> </div> <div id="sidebar"> <ul> <a href="http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565"><img src="https://www.scottaaronson.blog/Jacket.gif"></a> <br><a href="http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565">[Order from Amazon.com]</a> <br><a href="http://www.amazon.co.uk/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565/">[Order from Amazon.co.uk]</a> <br><a href="http://www.amazon.com/Quantum-Computing-since-Democritus-ebook/dp/B00B4V6IZK/">[Kindle edition]</a> <p> <li> <form method="get" id="searchform" action="https://scottaaronson.blog/"> <div><input type="text" value="" name="s" id="s" /> <input type="submit" id="searchsubmit" value="Search" /> </div> </form> </li>   <li> <p>You are currently browsing the <a href="https://scottaaronson.blog/">Shtetl-Optimized</a> weblog archives for August, 2007.</p> </li>  <li><h2>Archives</h2> <ul> <li><a href='https://scottaaronson.blog/?m=202504'>April 2025</a></li> <li><a href='https://scottaaronson.blog/?m=202503'>March 2025</a></li> <li><a href='https://scottaaronson.blog/?m=202502'>February 2025</a></li> <li><a href='https://scottaaronson.blog/?m=202501'>January 2025</a></li> <li><a href='https://scottaaronson.blog/?m=202412'>December 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202411'>November 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202410'>October 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202409'>September 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202408'>August 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202407'>July 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202406'>June 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202405'>May 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202404'>April 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202403'>March 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202402'>February 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202401'>January 2024</a></li> <li><a href='https://scottaaronson.blog/?m=202312'>December 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202311'>November 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202310'>October 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202309'>September 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202308'>August 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202307'>July 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202305'>May 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202304'>April 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202303'>March 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202302'>February 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202301'>January 2023</a></li> <li><a href='https://scottaaronson.blog/?m=202212'>December 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202211'>November 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202210'>October 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202209'>September 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202208'>August 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202207'>July 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202206'>June 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202205'>May 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202204'>April 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202202'>February 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202201'>January 2022</a></li> <li><a href='https://scottaaronson.blog/?m=202112'>December 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202111'>November 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202110'>October 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202109'>September 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202108'>August 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202107'>July 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202106'>June 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202105'>May 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202104'>April 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202103'>March 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202102'>February 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202101'>January 2021</a></li> <li><a href='https://scottaaronson.blog/?m=202012'>December 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202011'>November 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202010'>October 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202009'>September 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202008'>August 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202007'>July 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202006'>June 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202005'>May 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202004'>April 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202003'>March 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202002'>February 2020</a></li> <li><a href='https://scottaaronson.blog/?m=202001'>January 2020</a></li> <li><a href='https://scottaaronson.blog/?m=201912'>December 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201911'>November 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201910'>October 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201909'>September 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201908'>August 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201907'>July 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201906'>June 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201905'>May 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201904'>April 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201903'>March 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201902'>February 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201901'>January 2019</a></li> <li><a href='https://scottaaronson.blog/?m=201812'>December 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201811'>November 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201810'>October 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201809'>September 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201808'>August 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201807'>July 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201806'>June 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201805'>May 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201804'>April 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201803'>March 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201802'>February 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201801'>January 2018</a></li> <li><a href='https://scottaaronson.blog/?m=201712'>December 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201711'>November 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201710'>October 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201709'>September 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201708'>August 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201707'>July 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201706'>June 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201705'>May 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201704'>April 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201703'>March 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201701'>January 2017</a></li> <li><a href='https://scottaaronson.blog/?m=201612'>December 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201611'>November 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201610'>October 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201609'>September 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201607'>July 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201606'>June 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201605'>May 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201604'>April 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201603'>March 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201602'>February 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201601'>January 2016</a></li> <li><a href='https://scottaaronson.blog/?m=201512'>December 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201511'>November 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201510'>October 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201509'>September 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201508'>August 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201507'>July 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201506'>June 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201505'>May 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201504'>April 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201503'>March 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201502'>February 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201501'>January 2015</a></li> <li><a href='https://scottaaronson.blog/?m=201412'>December 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201411'>November 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201410'>October 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201409'>September 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201408'>August 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201407'>July 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201406'>June 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201405'>May 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201404'>April 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201403'>March 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201402'>February 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201401'>January 2014</a></li> <li><a href='https://scottaaronson.blog/?m=201312'>December 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201311'>November 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201310'>October 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201309'>September 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201308'>August 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201307'>July 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201306'>June 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201305'>May 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201304'>April 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201303'>March 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201302'>February 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201301'>January 2013</a></li> <li><a href='https://scottaaronson.blog/?m=201212'>December 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201211'>November 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201210'>October 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201209'>September 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201208'>August 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201207'>July 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201206'>June 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201205'>May 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201204'>April 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201203'>March 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201202'>February 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201201'>January 2012</a></li> <li><a href='https://scottaaronson.blog/?m=201112'>December 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201111'>November 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201110'>October 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201109'>September 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201108'>August 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201107'>July 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201106'>June 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201105'>May 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201104'>April 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201103'>March 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201102'>February 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201101'>January 2011</a></li> <li><a href='https://scottaaronson.blog/?m=201012'>December 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201011'>November 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201010'>October 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201009'>September 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201008'>August 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201007'>July 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201006'>June 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201005'>May 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201004'>April 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201002'>February 2010</a></li> <li><a href='https://scottaaronson.blog/?m=201001'>January 2010</a></li> <li><a href='https://scottaaronson.blog/?m=200912'>December 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200911'>November 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200910'>October 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200909'>September 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200908'>August 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200907'>July 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200906'>June 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200905'>May 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200904'>April 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200903'>March 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200902'>February 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200901'>January 2009</a></li> <li><a href='https://scottaaronson.blog/?m=200812'>December 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200811'>November 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200810'>October 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200809'>September 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200808'>August 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200807'>July 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200806'>June 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200805'>May 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200804'>April 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200803'>March 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200802'>February 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200801'>January 2008</a></li> <li><a href='https://scottaaronson.blog/?m=200712'>December 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200711'>November 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200710'>October 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200709'>September 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200708'>August 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200707'>July 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200706'>June 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200705'>May 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200704'>April 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200703'>March 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200702'>February 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200701'>January 2007</a></li> <li><a href='https://scottaaronson.blog/?m=200612'>December 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200611'>November 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200610'>October 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200609'>September 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200608'>August 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200607'>July 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200606'>June 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200605'>May 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200604'>April 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200603'>March 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200602'>February 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200601'>January 2006</a></li> <li><a href='https://scottaaronson.blog/?m=200512'>December 2005</a></li> <li><a href='https://scottaaronson.blog/?m=200511'>November 2005</a></li> <li><a href='https://scottaaronson.blog/?m=200510'>October 2005</a></li> </ul> </li> <li class="categories"><h2>Categories</h2><ul> <li class="cat-item cat-item-10"><a href="https://scottaaronson.blog/?cat=10">Adventures in Meatspace</a> (146) </li> <li class="cat-item cat-item-31"><a href="https://scottaaronson.blog/?cat=31">Announcements</a> (214) </li> <li class="cat-item cat-item-34"><a href="https://scottaaronson.blog/?cat=34">Ask Me Anything</a> (9) </li> <li class="cat-item cat-item-33"><a href="https://scottaaronson.blog/?cat=33">Bell's Theorem? But a Flesh Wound!</a> (11) </li> <li class="cat-item cat-item-5"><a href="https://scottaaronson.blog/?cat=5">Complexity</a> (322) </li> <li class="cat-item cat-item-14"><a href="https://scottaaronson.blog/?cat=14">Contests</a> (11) </li> <li class="cat-item cat-item-15"><a href="https://scottaaronson.blog/?cat=15">CS/Physics Deathmatch</a> (28) </li> <li class="cat-item cat-item-6"><a href="https://scottaaronson.blog/?cat=6">Democritus</a> (25) </li> <li class="cat-item cat-item-18"><a href="https://scottaaronson.blog/?cat=18">Embarrassing Myself</a> (58) </li> <li class="cat-item cat-item-27"><a href="https://scottaaronson.blog/?cat=27">GITCS</a> (5) </li> <li class="cat-item cat-item-13"><a href="https://scottaaronson.blog/?cat=13">Mahmoud</a> (8) </li> <li class="cat-item cat-item-12"><a href="https://scottaaronson.blog/?cat=12">Metaphysical Spouting</a> (81) </li> <li class="cat-item cat-item-30"><a href="https://scottaaronson.blog/?cat=30">Mirrored on CSAIL Blog</a> (44) </li> <li class="cat-item cat-item-9"><a href="https://scottaaronson.blog/?cat=9">Mistake of the Week</a> (13) </li> <li class="cat-item cat-item-11"><a href="https://scottaaronson.blog/?cat=11">Nerd Interest</a> (233) </li> <li class="cat-item cat-item-29"><a href="https://scottaaronson.blog/?cat=29">Nerd Self-Help</a> (16) </li> <li class="cat-item cat-item-42"><a href="https://scottaaronson.blog/?cat=42">Obviously I'm Not Defending Aaronson</a> (46) </li> <li class="cat-item cat-item-19"><a href="https://scottaaronson.blog/?cat=19">Physics for Doofuses</a> (10) </li> <li class="cat-item cat-item-32"><a href="https://scottaaronson.blog/?cat=32">PlanetMO</a> (1) </li> <li class="cat-item cat-item-3"><a href="https://scottaaronson.blog/?cat=3">Procrastination</a> (131) </li> <li class="cat-item cat-item-4"><a href="https://scottaaronson.blog/?cat=4">Quantum</a> (309) </li> <li class="cat-item cat-item-24"><a href="https://scottaaronson.blog/?cat=24">Quantum Computing Primers</a> (1) </li> <li class="cat-item cat-item-23"><a href="https://scottaaronson.blog/?cat=23">Quantum Computing Since Democritus</a> (3) </li> <li class="cat-item cat-item-16"><a href="https://scottaaronson.blog/?cat=16">Rage Against Doofosity</a> (104) </li> <li class="cat-item cat-item-7"><a href="https://scottaaronson.blog/?cat=7">Self-Referential</a> (50) </li> <li class="cat-item cat-item-17"><a href="https://scottaaronson.blog/?cat=17">Speaking Truth to Parallelism</a> (60) </li> <li class="cat-item cat-item-8"><a href="https://scottaaronson.blog/?cat=8">The Fate of Humanity</a> (185) </li> <li class="cat-item cat-item-1"><a href="https://scottaaronson.blog/?cat=1">Uncategorized</a> (5) </li> </ul></li> </ul>  </div> <hr /> <div id="footer">  <p> Shtetl-Optimized is proudly powered by <a href="https://wordpress.com/wp/?partner_domain=scottaaronson.blog&utm_source=Automattic&utm_medium=colophon&utm_campaign=Concierge%20Referral&utm_term=scottaaronson.blog" class="imprint" target="_blank">WordPress</a> <br /><a href="https://scottaaronson.blog/?feed=rss2">Entries (RSS)</a> and <a href="https://scottaaronson.blog/?feed=comments-rss2">Comments (RSS)</a>.  </p> </div> </div>  <div id="fb-root"></div> <script>(function(d, s, id) { var js, fjs = d.getElementsByTagName(s)[0]; if (d.getElementById(id)) return; js = d.createElement(s); js.id = id; js.src = "//connect.facebook.net/en_US/sdk.js#xfbml=1&version=v2.0"; fjs.parentNode.insertBefore(js, fjs); }(document, 'script', 'facebook-jssdk'));</script><script type="text/javascript" id="jetpack-stats-js-before"> /* <![CDATA[ */ _stq = window._stq || []; _stq.push([ "view", JSON.parse("{\"v\":\"ext\",\"blog\":\"129520580\",\"post\":\"0\",\"tz\":\"-5\",\"srv\":\"scottaaronson.blog\",\"hp\":\"atomic\",\"ac\":\"3\",\"amp\":\"0\",\"j\":\"1:14.6-a.1\"}") ]); _stq.push([ "clickTrackerInit", "129520580", "0" ]); /* ]]> */ </script> <script type="text/javascript" src="https://stats.wp.com/e-202515.js" id="jetpack-stats-js" defer="defer" data-wp-strategy="defer"></script> <script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.9/MathJax.js?config=default&ver=1.3.13" id="mathjax-js"></script> <script type="text/javascript"> (function() { var t = document.createElement( 'script' ); t.type = 'text/javascript'; t.async = true; t.id = 'gauges-tracker'; t.setAttribute( 'data-site-id', '6165d574ad4fe5563e1e4971' ); t.src = '//secure.gaug.es/track.js'; var s = document.getElementsByTagName( 'script' )[0]; s.parentNode.insertBefore( t, s ); })(); </script> </body></html>