Update (Oct. 3): OK, a sixth announcement. I just posted a question on CS Theory StackExchange, entitled Overarching reasons why problems are in P or BPP. 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 Clay Institute workshop on New Insights into Computational Intractability. The workshop is concurrent with three others, including one on Number Theory and Physics that includes an amplituhedron-related talk by Andrew Hodges. (Speaking of which, see here for a small but non-parodic observation about expressing amplitudes as volumes of polytopes.)
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 over in Cambridge. But alas I had to cancel, since my diaper-changing services are needed in the other Cambridge. So, if anyone in Cambridge (or anywhere else in the United Kingdom) really wants to talk to me, come to Oxford this week!
3. Back in June, Jens Eisert and three others posted a preprint claiming that the output of a BosonSampling device would be “indistinguishable from the uniform distribution” in various senses. 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. OK, so just this weekend, we posted our own 41-page preprint, entitled “BosonSampling Is Far From Uniform.” I hope it suffices by way of reply! (Incidentally, this is also the paper I hinted at in a previous post: the one where π2/6 and the Euler-Mascheroni constant make cameo appearances.) To clarify, if we just 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). 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.
4. Also on the arXiv last night, there was a phenomenal survey about the quantum PCP conjecture by Dorit Aharonov, Itai Arad, and my former postdoc Thomas Vidick (soon to be a professor at Caltech). 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” seven years ago.
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! Indeed, it’s October 4 (three days from now). See here for details, and here for information about student travel support. (The links were down when I just tried them, but hopefully the server will be back up soon.)