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 » 2011 » March</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="2 posts published by Scott during December 1999" />  <meta property="og:type" content="website" /> <meta property="og:title" content="March 2011 – 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 March, 2011</h2> <div class="navigation"> <div class="alignleft"></div> <div class="alignright"></div> </div> <div class="post"> <h3 id="post-570"><a href="https://scottaaronson.blog/?p=570" rel="bookmark" title="Permanent Link to Valiant’s valiance recognized">Valiant’s valiance recognized</a></h3> <small>Wednesday, March 9th, 2011</small> <div class="entry"> <p><strong><span style="color: #ff0000;">Update (March 25):</span></strong> I have a new paper called <a href="http://www.scottaaronson.com/papers/sharp.pdf">A Linear-Optical Proof that the Permanent is #P-Hard</a>, which is dedicated to Les Valiant on the occasion of his Turing Award. Here’s the abstract:</p> <p style="padding-left: 30px;">One of the crown jewels of complexity theory is Valiant’s 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of <em>linear-optical quantum computing</em>—and in particular, a universality theorem due to Knill, Laflamme, and Milburn—one can give a different and arguably more intuitive proof of this theorem.</p> <hr /> <p>For decades, Harvard’s <a href="http://en.wikipedia.org/wiki/Leslie_Valiant">Leslie Valiant</a> has obviously deserved a Turing Award—and today, the ACM <a href="http://www.acm.org/news/featured/turing-award-2010">most excellently announced its agreement</a> with the obvious. I have little to add to the <a href="http://awards.acm.org/2011/TuringAwardCommitteeCommentary.pdf">prize citation</a> (see also <a href="http://blog.computationalcomplexity.org/2011/03/les-valiant-wins-turing-award.html">Lance’s post</a>): from launching new fields whose reach extends beyond theory (PAC-learning), to proving epochal results (#P-completeness of the permanent), to asking hugely influential questions (permanent vs. determinant), Valiant has been a creative powerhouse of theoretical computer science for longer than I’ve been alive.</p> <p>One thing the prize citation <em>doesn’t</em> mention is that Valiant is now the third Turing Award winner (after Andy Yao and Len Adleman) to have made a major contribution to quantum computing theory. Valiant’s 2001 paper <a href="http://people.seas.harvard.edu/~valiant/stoc01.pdf">Quantum Computers that can be Simulated Classically in Polynomial Time</a> introduced the beautiful computational model that computer scientists now know as “matchgates,”<em> </em>and that <a href="http://arxiv.org/abs/quant-ph/0108010">physicists know as “noninteracting fermions.”</a> It still amazes that Valiant proposed this model for purely mathematical reasons—hitting physical relevance straight between the eyes despite (as far as I can tell) not having that target anywhere in his sights.</p> <p>To put the point in terms that my physicist friends will understand, that Valiant himself would probably dispute, but that I would defend:</p> <p style="padding-left: 30px;"><em>Valiant’s work has shown that, even if our universe hadn’t been made of bosons and fermions, theoretical computer scientists would have had compelling reasons of their own to invent those particles or something equivalent to them—and furthermore, that at least one theoretical computer scientist would have had the imagination to do so.</em></p> <p><em>Certainly</em> Valiant has had a huge influence on me, both through his work and as someone who made time to talk to me as an obscure grad student a decade ago. Three of my papers—<a href="http://www.scottaaronson.com/papers/occamprs.pdf">The Learnability of Quantum States</a>, <a href="http://www.scottaaronson.com/papers/limadv.pdf">A Full Characterization of Quantum Advice</a>, and <a href="http://www.scottaaronson.com/papers/optics.pdf">The Computational Complexity of Linear Optics</a>—would collapse entirely without Valiant-laid foundations.</p> <p>Congratulations, Les!</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=570" 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="Valiant’s valiance recognized" data-url="https://scottaaronson.blog/?p=570" 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=570" ></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=570" 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=31" rel="category">Announcements</a>, <a href="https://scottaaronson.blog/?cat=5" rel="category">Complexity</a>, <a href="https://scottaaronson.blog/?cat=15" rel="category">CS/Physics Deathmatch</a>, <a href="https://scottaaronson.blog/?cat=4" rel="category">Quantum</a> | <a href="https://scottaaronson.blog/?p=570#comments">28 Comments »</a></p> </div> <div class="post"> <h3 id="post-566"><a href="https://scottaaronson.blog/?p=566" rel="bookmark" title="Permanent Link to Science journalism: good and hilarious">Science journalism: good and hilarious</a></h3> <small>Saturday, March 5th, 2011</small> <div class="entry"> <p>On Wednesday, Larry Hardesty of the MIT News Office <a href="http://web.mit.edu/newsoffice/2011/quantum-experiment-0302.html">published a nice article</a> about <a href="http://www.scottaaronson.com/papers/optics.pdf">my work with Alex Arkhipov</a> on the computational complexity of linear optics. Although the title—“The quantum singularity”—made me wince a little, I was impressed by the effort Larry put into getting the facts right, and especially laying out the problems that still need to be solved.</p> <p>Less successful was a <a href="http://www.pcmag.com/article2/0,2817,2381285,00.asp">story in PC Magazine</a> based on MIT’s press release, which contained the following sentence (let me know if you can decipher what the author meant—I couldn’t):</p> <p style="padding-left: 30px;">Aaronson says that he and Arkhipov have not successfully proven that designing a device capable of testing the theory is impossible—which is an important first step, whether to eventually building a quantum computer, or even just laying the initial framework for using the microscopic secrets of the universe to let humans better understand the world that surrounds them.</p> <p>However, in the competition for Popular Science Article Sentence of the Year, the sentence above will have to contend with a now-classic sentence from the <a href="http://www.nytimes.com/2011/02/17/science/17jeopardy-watson.html"><em>New York Times</em> article about Watson</a>:</p> <p style="padding-left: 30px;">More than anything, the contest was a vindication for the academic field of computer science, which began with great promise in the 1960s with the vision of creating a thinking machine and which became the laughingstock of Silicon Valley in the 1980s, when a series of heavily financed start-up companies went bankrupt.</p> <p><strong> </strong></p> <p>To the NYT’s credit, they quickly posted a correction:</p> <p style="padding-left: 30px;">An article last Thursday about the I.B.M. computer Watson misidentified the academic field vindicated by Watson’s besting of two human opponents on “Jeopardy!” It is artificial intelligence — not computer science, a broader field that includes artificial intelligence.</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=566" 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="Science journalism: good and hilarious" data-url="https://scottaaronson.blog/?p=566" 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=566" ></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=566" 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=11" rel="category">Nerd Interest</a>, <a href="https://scottaaronson.blog/?cat=4" rel="category">Quantum</a> | <a href="https://scottaaronson.blog/?p=566#comments">19 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 March, 2011.</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>