{"id":2284,"date":"2015-05-16T23:08:47","date_gmt":"2015-05-17T03:08:47","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2284"},"modified":"2016-12-10T04:50:25","modified_gmt":"2016-12-10T09:50:25","slug":"five-announcements-2","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2284","title":{"rendered":"Five announcements"},"content":{"rendered":"

1. Sanjeev Arora sent me a heads-up that there’s a discussion about the future of the STOC conference<\/a>\u00a0\u00a0at the Windows on Theory<\/em> blog—in particular, about the idea of turning STOC into a longer “CS theory festival.” \u00a0If you have opinions about this, don’t miss the chance to make your voice heard.<\/p>\n

2. Back in January, I blogged about a new quantum optimization algorithm<\/a> by Farhi, Goldstone, and Gutmann, which was notable for being, as far as anyone could tell, the first quantum algorithm to achieve a provably better approximation ratio than the best-known classical algorithm for an NP-hard optimization problem. \u00a0Today, I report that a fearsome list of authors—Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright—has put out an eagerly-awaited paper<\/a>\u00a0that gives a classical algorithm for the same problem, with better\u00a0performance than the quantum algorithm’s. \u00a0(They write that\u00a0this “improves both qualitatively and quantitatively” on Farhi et al.’s work; I assume “qualitatively” refers to the fact that the new algorithm is classical.) \u00a0What happened, apparently, is that after I blogged (with enthusiasm) about the Farhi et al. result, a bunch of classical complexity theorists\u00a0read my post and decided\u00a0independently that they could match or beat the quantum algorithm’s performance classically; then they found out about each other and decided to merge their efforts. \u00a0I’m proud to say that this isn’t the first example of this blog catalyzing actual research progress, though it’s probably the best example\u00a0so far. \u00a0[Update: Luca Trevisan now has a great post explaining what happened in much more detail, entitled “How Many Theoreticians Does It Take to Approximate Max 3Lin?”]<\/a><\/p>\n

Another update: Farhi et al. have posted a new version<\/a> of their paper, in which they can almost match the performance of the classical algorithm using their quantum algorithm.<\/p>\n

3. Jennifer Ouellette has a wonderful article<\/a> in Quanta<\/em>\u00a0magazine about recent progress in AdS\/MERA (i.e., “the emergence of spacetime from entanglement”), centered around the ideas of Brian Swingle. \u00a0This is one of the main\u00a0things that I’d love\u00a0to understand better right now—if I succeed even partially, you’ll know because I’ll write a blog post trying to explain it to others. \u00a0See also this blog post<\/a> by Sean Carroll (about this paper<\/a> by Ning Bao et al.), and this paper<\/a> by Pastawski, Yoshida, Harlow, and Preskill, which explicitly mines\u00a0the AdS\/CFT correspondence for\u00a0examples of quantum error-correcting codes.<\/p>\n

4. Celebrity rationalist Julia Galef, who I had the great honor of meeting recently, has a podcast interview<\/a> with Sean Carroll about why Carroll accepts\u00a0the many-worlds interpretation. \u00a0(Or if, like me, you prefer the written word to the spoken one, click here<\/a> for a full transcript.) \u00a0Unfortunately, Sean is given\u00a0the opportunity at the end of the interview to recommend one science book to his listeners—just one!—but\u00a0he squanders it by plugging some weird, self-indulgent thing called Quantum Computing Since Democritus<\/a><\/em>. \u00a0Julia also has a YouTube video<\/a> about what she learned from the interview, but I haven’t yet watched it\u00a0(is there\u00a0a\u00a0transcript?).<\/p>\n

5. I came across an\u00a0insightful if meandering essay<\/a>\u00a0about nerd culture by Meredith L. Patterson. \u00a0In particular, noticing how\u00a0the term “nerd” has been co-opted by normal, socially-skilled people, who’ve\u00a0quickly\u00a0set about remaking nerd social norms\u00a0to make them identical to the rest of the world’s norms,\u00a0Patterson\u00a0coins the term “weird-nerd” to describe people like herself, who are still nerds in the original sense<\/em> and who don’t\u00a0see nerd culture as something horribly, irreparably broken. \u00a0As she writes: “We’ll start to feel less defensive when we get some indication\u200a—\u200aany indication\u200a—\u200athat our critics understand what parts of our culture we don’t want to lose and why we don\u2019t want to lose them.” \u00a0(But is this the start\u00a0of\u00a0a linguistic treadmill? \u00a0Will we eventually need to talk about weird<\/em>-weird-nerds, etc.?)<\/p>\n","protected":false},"excerpt":{"rendered":"

1. Sanjeev Arora sent me a heads-up that there’s a discussion about the future of the STOC conference\u00a0\u00a0at the Windows on Theory blog—in particular, about the idea of turning STOC into a longer “CS theory festival.” \u00a0If you have opinions about this, don’t miss the chance to make your voice heard. 2. Back in January, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[31,5,11],"tags":[],"class_list":["post-2284","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity","category-nerd-interest"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2284","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\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2284"}],"version-history":[{"count":6,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2284\/revisions"}],"predecessor-version":[{"id":2373,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2284\/revisions\/2373"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}