Aaronson-Ambainis Conjecture proved! (By AI, of course)

We now, of course, live in age where longstanding open problems in quantum computing theory (and all theoretical computer science, and all math) are dropping like flies, to the extent that there’s no way I could possibly do a post on each and every bombshell. But I can’t exactly avoid the Aaronson-Ambainis Conjecture, given that my name is on it, and that I cared about the answer to this one (back in 2019, I even blogged about an attempted solution that ultimately turned out to be fallacious). For those tuning in from home, the AA Conjecture, which Andris and I posed back in 2009, says that every bounded degree-d polynomial p:{0,1}n→[0,1] in n Boolean variables, with constant variance, has some variable whose influence is at least 1/poly(d). The reason Andris and I cared about this conjecture is that, as we proved, it implies that there’s no superpolynomial advantage of quantum query complexity over classical query complexity for decision problems that works on most Boolean inputs.…

Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town