  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 $\leq \text{poly}(q)$, Aaronson and Ambainis
proposed the following conjecture: let $f: \{ \pm 1\}^n \rightarrow [0,1]$ be a
degree $d$ polynomial with variance $\geq \epsilon$. Then, there exists a
coordinate of $f$ with influence $\geq \text{poly} (\epsilon, 1/d)$.
  We show that for any polynomial $f: \{ \pm 1\}^n \rightarrow [0,1]$ of degree
$d$ $(d \geq 2)$ and variance $\text{Var}[f] \geq 1/d$, if $\rho$ denotes a
random restriction with survival probability $\dfrac{\log(d)}{C_1 d}$, $$
\text{Pr} \left[f_{\rho} \text{ has a coordinate with influence} \geq
\dfrac{\text{Var}[f]^2 }{d^{C_2}} \right] \geq \dfrac{\text{Var}[f]
\log(d)}{50C_1 d}$$ where $C_1, C_2>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.
