We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right] $ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right) $ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

We investigate the complexity of integration and
derivative for multivariate polynomials in the standard computation
model. The integration is in the unit cube $[0,1]^d$ for a
multivariate polynomial, which has format
$f(x_1,\cdots,
x_d)=p_1(x_1,\cdots, x_d)p_2(x_1,\cdots, x_d)\cdots p_k(x_1,\cdots,
x_d)$,
where each $p_i(x_1,\cdots, x_d)=\sum_{j=1}^d q_j(x_j)$ with
all single variable polynomials $q_j(x_j)$ ... more >>>

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in ... more >>>