Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-035 | 26th February 2024 19:35

Aaronson-Ambainis Conjecture Is True For Random Restrictions

RSS-Feed




Revision #1
Authors: Sreejata Bhattacharya
Accepted on: 26th February 2024 19:35
Downloads: 191
Keywords: 


Abstract:

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 $\log(d)/(C_1 d)$,
$$ \text{Pr} \left[f_{\rho} \text{ has a coordinate with influence} \geq \frac{\text{Var}[f]^2 }{d^{C_2}} \right] \geq \frac{\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.



Changes to previous version:

(1) Fixed a formatting error in abstract (formatting was off when viewed on Android)
(2) Fixed some typos.


Paper:

TR24-035 | 20th February 2024 15:49

Aaronson-Ambainis Conjecture Is True For Random Restrictions





TR24-035
Authors: Sreejata Bhattacharya
Publication: 25th February 2024 07:28
Downloads: 350
Keywords: 


Abstract:

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 $\frac{\log(d)}{C_1 d}$,
$$ \text{Pr} \left[f_{\rho} \text{ has a coordinate with influence} \geq \frac{\text{Var}[f]^2 }{d^{C_2}} \right] \geq \frac{\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.



ISSN 1433-8092 | Imprint