{"id":249,"date":"2007-06-17T07:54:00","date_gmt":"2007-06-17T15:54:00","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=249"},"modified":"2007-06-17T07:54:00","modified_gmt":"2007-06-17T15:54:00","slug":"you-down-with-spp","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=249","title":{"rendered":"You down with SPP?"},"content":{"rendered":"<p>I&#8217;ve been in San Diego all week for the <a href=\"http:\/\/www.acm.org\/fcrc\/\">FCRC<\/a> (Federated Computing Research Conference), which just wrapped up yesterday.  I was here for <a href=\"http:\/\/facweb.cs.depaul.edu\/jrogers\/complexity\/\">Complexity&#8217;2007<\/a>, but, lawless rebel that I am, I also crashed some of the talks at <a href=\"http:\/\/www.research.att.com\/~dsj\/stoc07.html\">STOC&#8217;2007<\/a>.  Highlights:<\/p>\n<ul>\n<li>Many of my friends wanted to skip the plenary talk on &#8220;Computer Science: Past, Present, and Future,&#8221; by past Computing Research Association Chair <a href=\"http:\/\/lazowska.cs.washington.edu\/\">Ed Lazowska<\/a>.  But I urged them to go despite the title, since I&#8217;d met Lazowska when I interviewed at the University of Washington, and immediately concluded that <em>this is the guy we want in charge of our field<\/em>.  As it turned out,  Lazowska gave the most rousing defense of computer science research I&#8217;ve ever heard. Here&#8217;s what I remember: 2004 was the first year that human beings produced more transistors than grains of rice (~10 quintillion). Academic computer science research more than paid for itself over the last two decades by producing at least 15 billion-dollar industries. Computer scientists should be tackling the biggest issues in the world, including climate change and third-world poverty (Lazowska mentioned a project he&#8217;s involved with to put thousands of sensors under the ocean near the Northwest US, thereby &#8220;reducing oceanography to a computer science problem,&#8221; as well as a project of his student <a href=\"http:\/\/www.cs.washington.edu\/homes\/tapan\/\">Tapan Parikh<\/a>, to let illiterate farmers in India and Guatemala upload financial records via cellphones with intermittent access). Computer scientists should bring self-driving cars from prototype to reality, thereby saving some of the 45,000 people in the US alone who die in auto accidents every year. The future of theoretical computer science lies in transforming the other sciences (math, physics, economics, biology) via computational thinking.  Had Watson and Crick been computer scientists, they would&#8217;ve realized immediately that the real import of their discovery had nothing to do with the biochemical details, and everything to do with the fact that DNA is a digital code. A piece of computer science (P vs. NP) is what many now consider the preeminent open problem in mathematics.  Quantum computing might not work but certainly merits a huge effort.  Our introductory CS courses suck.  We&#8217;ve been doing a terrible job recruiting women.<font color=\"red\"><strong> <\/strong><\/font><font color=\"red\"><strong>Update (6\/23):<\/strong><\/font> Slides for Ed Lazowska&#8217;s talk, as well as another inspiring talk by Christos Papadimitriou, can be found <a href=\"http:\/\/lazowska.cs.washington.edu\/fcrc\/\">here<\/a>.<\/li>\n<\/ul>\n<ul>\n<li>I gave a <a href=\"http:\/\/www.scottaaronson.com\/talks\/qcap.ppt\">talk<\/a> on my <a href=\"http:\/\/www.scottaaronson.com\/papers\/qcap.pdf\">paper<\/a> with Greg Kuperberg, on quantum versus classical proofs and advice.<\/li>\n<\/ul>\n<ul>\n<li>I gave <a href=\"http:\/\/www.scottaaronson.com\/talks\/andris.ppt\">another talk<\/a> on the paper <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0701126\">&#8220;Quantum t-designs&#8221;<\/a>, by my colleagues Andris Ambainis and Joe Emerson. Why?  Because Joe couldn&#8217;t make it to San Diego, and Andris lost his passport.  As I promised Andris, the vast majority of the talk was <em>not<\/em> delivered in my imitation of his voice.<\/li>\n<\/ul>\n<ul>\n<li><a href=\"http:\/\/theory.lcs.mit.edu\/~yekhanin\/\">Sergey Yekhanin<\/a> gave a talk on his <a href=\"http:\/\/theory.lcs.mit.edu\/~yekhanin\/Papers\/nice_PIR.pdf\">paper<\/a> &#8220;Towards 3-query locally decodable codes of subexponential length,&#8221; which not only won the Danny Lewin Best Student Paper Award but <em>also<\/em> shared the STOC&#8217;07 Best Paper Award.  Not to toot my own breakthrough-recognition horn, but &#8230; you <a href=\"https:\/\/scottaaronson.blog\/?p=142\">saw it here first<\/a>.<\/li>\n<\/ul>\n<ul>\n<li><a href=\"http:\/\/www.cs.cmu.edu\/~ryanw\/\">Ryan Williams<\/a>, the pride of Alabama, won the Complexity Best Student Paper Award for his <a href=\"http:\/\/eccc.hpi-web.de\/eccc-reports\/2007\/TR07-036\/index.html\">excellent paper<\/a> &#8220;Time-space tradeoffs for counting NP solutions modulo integers.&#8221;  This marks the second time Ryan has won this award, as well as the first time the award has been given twice to a former Cornell undergrad and resident of <a href=\"http:\/\/www.tellurideassociation.org\/cbfront.html\">Telluride House<\/a> in the late 1990&#8217;s (no &#8230; wait). So what did Ryan prove?  Alright, suppose you have O(n<sup>1.8<\/sup>) time and n<sup>o(1)<\/sup> memory, and you want to count the number of satisfying assignments of a Boolean formula, modulo a prime number p. Then there&#8217;s at most one prime p for which you can do this. Ryan has no idea <em>which<\/em> prime, and conjectures in any case that it doesn&#8217;t exist.  I&#8217;m not making this up.<\/li>\n<\/ul>\n<ul>\n<li><a href=\"http:\/\/dimacs.rutgers.edu\/~gkindler\/\">Guy Kindler<\/a> gave a talk on his <a href=\"http:\/\/eccc.hpi-web.de\/eccc-reports\/2007\/TR07-043\/index.html\">amazing paper<\/a> with <a href=\"http:\/\/www.wisdom.weizmann.ac.il\/~feige\/\">Uri Feige<\/a> and <a href=\"http:\/\/www.cs.cmu.edu\/~odonnell\/\">Ryan O&#8217;Donnell<\/a>, &#8220;Understanding parallel repetition requires understanding foams.&#8221;  Read the paper: the title is literally true.<\/li>\n<\/ul>\n<ul>\n<li>I saw <a href=\"http:\/\/www.math.ucla.edu\/~tao\/\">Terence Tao<\/a>.<\/li>\n<\/ul>\n<ul>\n<li><a href=\"http:\/\/homepages.cwi.nl\/~rdewolf\/\">Ronald de Wolf<\/a> and <a href=\"http:\/\/homepages.cwi.nl\/~buhrman\/\">Harry Buhrman<\/a> are reading this entry over my shoulder right now as I sit in the airport terminal typing.<\/li>\n<\/ul>\n<ul>\n<li>As I watched the conference regulars &#8212; Lance Fortnow, Bill Gasarch, Harry Buhrman (yes, Harry, you got another mention &#8212; happy?), Ken Regan, etc. &#8212; banter and drink coffee, I realized that the IEEE Conference on Computational Complexity <em>desperately needs an official theme song<\/em>. The song should have real complexity-theoretic content, but nevertheless be a little edgier than <a href=\"http:\/\/valis.cs.uiuc.edu\/~sariel\/misc\/funny\/#longest-path\">Find the Longest Path<\/a>.  So without further ado, I present to you a preliminary effort along these lines, due to Troy Lee and myself (aka &#8220;Nerdy by Nature&#8221;):<br \/>\n<blockquote><p><em>You down with <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#spp\">SPP<\/a> (Yeah you know me)<br \/>\nYou down with SPP (Yeah you know me)<br \/>\nYou down with SPP (Yeah you know me)<br \/>\nWho&#8217;s down with SPP (Every last attendee)<\/em><\/p><\/blockquote>\n<p>(Note: <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#bpp\">BPP<\/a> and <a href=\"http:\/\/qwiki.caltech.edu\/wiki\/Complexity_Zoo#zpp\">ZPP<\/a> also would&#8217;ve fit the meter, but those are really more appropriate for STOC than Complexity.)<\/p>\n<p><strong><font color=\"red\">Update (6\/20):<\/font><\/strong> We may <a href=\"http:\/\/weblog.fortnow.com\/2007\/06\/complexity-theory-theme-song-options.html#4032691377325832224\">have a winner<\/a>, Aaron Sterling&#8217;s <em>I Just Do Theory<\/em>.  (Thanks to Bill Gasarch for the pointer.)<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ve been in San Diego all week for the FCRC (Federated Computing Research Conference), which just wrapped up yesterday. I was here for Complexity&#8217;2007, but, lawless rebel that I am, I also crashed some of the talks at STOC&#8217;2007. Highlights: Many of my friends wanted to skip the plenary talk on &#8220;Computer Science: Past, Present, [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[10,5],"tags":[],"class_list":["post-249","post","type-post","status-publish","format-standard","hentry","category-adventures-in-meatspace","category-complexity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/249","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=249"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/249\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=249"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=249"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=249"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}