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 Var[f] ≥ 1/d, if ρ denotes a random restriction with survival probability log(d)/C₁ d, Pr [fρ has a coordinate with influence ≥ Var[f]² dC₂ ] ≥ Var[f] log(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.