The determinantal complexity of a polynomial $P \in \mathbb{F}[x_1, \ldots, x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1, \ldots, x_n]$ such that $P = Det(M)$. We prove that the determinantal complexity of the polynomial $\sum_{i = 1}^n x_i^n$ ... more >>>

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 >>>

Aaronson and Ambainis (SICOMP '18) showed that any partial function on $N$ bits that can be computed with an advantage $\delta$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $\delta/2$ by a randomized decision tree making ${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries. Moreover, they conjectured ... more >>>