Aaronson-Ambainis Conjecture Is True For Random Restrictions

In an attempt to show that the acceptance probability of a quantum query algorithm making q queries can be well-approximated almost everywhere by a classical decision tree of depth poly (q), Aaronson and Ambainis proposed the following conjecture: let f: \ 1\ⁿ 0, 1 be a degree d polynomial with variance. Then, there exists a coordinate of f with influence poly (, 1/d). We show that for any polynomial f: \ 1\ⁿ 0, 1 of degree d (d 2) and variance Varf 1/d, if denotes a random restriction with survival probability (d) C₁ d, Pr _ has a coordinate with influence Var[f² d^{C₂} ] Varf (d) 50C₁ d where C₁, C₂>0 are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.