{"id":1552,"date":"2013-10-01T00:35:42","date_gmt":"2013-10-01T05:35:42","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1552"},"modified":"2016-12-10T04:46:04","modified_gmt":"2016-12-10T09:46:04","slug":"five-announcements","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1552","title":{"rendered":"Five announcements"},"content":{"rendered":"

Update (Oct. 3):<\/strong><\/span> OK, a sixth announcement.\u00a0 I just posted a question on CS Theory StackExchange, entitled Overarching reasons why problems are in P or BPP<\/a>.\u00a0 If you have suggested additions or improvements to my rough list of “overarching reasons,” please post them over there — thanks!<\/p>\n

\n

1. I’m in Oxford right now, for a Clay Institute workshop on New Insights into Computational Intractability<\/a>.\u00a0 The workshop is concurrent with three others, including one on Number Theory and Physics<\/a> that includes an amplituhedron-related talk by Andrew Hodges.\u00a0 (Speaking of which, see here<\/a> for a small but non-parodic observation about expressing amplitudes as volumes of polytopes.)<\/p>\n

2. I was hoping to stay in the UK one more week, to attend the Newton Institute’s special semester on Mathematical Challenges in Quantum Information<\/a> over in Cambridge.\u00a0 But alas I had to cancel, since my diaper-changing services are needed in the other Cambridge.\u00a0 So, if anyone in Cambridge (or anywhere else in the United Kingdom) really<\/em> wants to talk to me, come to Oxford this week!<\/p>\n

3. Back in June, Jens Eisert and three others posted a preprint<\/a> claiming that the output of a BosonSampling device would be “indistinguishable from the uniform distribution” in various senses.\u00a0 Ever since then, people have emailing me, leaving comments on this blog, and cornering me at conferences to ask whether Alex Arkhipov and I had any response to these claims.\u00a0 OK, so just this weekend, we posted our own 41-page preprint, entitled “BosonSampling Is Far From Uniform.”<\/a>\u00a0 I hope it suffices by way of reply!\u00a0 (Incidentally, this is also the paper I hinted at in a previous post<\/a>: the one where \u03c02<\/sup>\/6 and the Euler-Mascheroni constant make cameo appearances.)\u00a0 To clarify, if we just<\/em> wanted to answer the claims of the Eisert group, then I think a couple paragraphs would suffice for that (see, for example, these PowerPoint slides<\/a>).\u00a0 In our new paper, however, Alex and I take the opportunity to go further: we study lots of interesting questions about the statistical properties of Haar-random BosonSampling distributions, and about how one might test efficiently whether a claimed BosonSampling device worked, even with hundreds or thousands of photons.<\/p>\n

4. Also on the arXiv last night, there was a phenomenal survey about the quantum PCP conjecture<\/a> by Dorit Aharonov, Itai Arad, and my former postdoc Thomas Vidick (soon to be a professor at Caltech).\u00a0 I recommend reading it in the strongest possible terms, if you’d like to see how far people have come with this problem (but also, how far they still have to go) since my “Quantum PCP Manifesto”<\/a> seven years ago.<\/p>\n

5. Christos Papadimitriou asked me to publicize that the deadline for early registration and hotel reservations for the upcoming FOCS in Berkeley is fast approaching!\u00a0 Indeed, it’s October 4 (three days from now).\u00a0 See here<\/a> for details, and here<\/a> for information about student travel support.\u00a0 (The links were down when I just tried them, but hopefully the server will be back up soon.)<\/p>\n","protected":false},"excerpt":{"rendered":"

Update (Oct. 3): OK, a sixth announcement.\u00a0 I just posted a question on CS Theory StackExchange, entitled Overarching reasons why problems are in P or BPP.\u00a0 If you have suggested additions or improvements to my rough list of “overarching reasons,” please post them over there — thanks! 1. I’m in Oxford right now, for a […]<\/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_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","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},"categories":[10,31,11],"tags":[],"class_list":["post-1552","post","type-post","status-publish","format-standard","hentry","category-adventures-in-meatspace","category-announcements","category-nerd-interest"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1552","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=1552"}],"version-history":[{"count":3,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1552\/revisions"}],"predecessor-version":[{"id":1557,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1552\/revisions\/1557"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}