All reports by Author Andrey Storozhenko:

__
TR20-128
| 3rd September 2020
__

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu#### An Optimal Separation of Randomized and Quantum Query Complexity

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{{d\choose\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound is essentially tight and settles a ... more >>>