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

The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs and to resolve this question it suffices to consider the case of query complexity $3$. We argue that to refute the existence of such an asymptotically good family ... more >>>