In this work we give a randomized blackbox polynomial identity testing (PIT) algorithm for constant-depth homogeneous noncommutative circuits, with poly-logarithmic time complexity in the circuit size. In fact, we show that the polynomial computable by such a depth-$(\Delta-1)$ circuit of size $s$ cannot be a polynomial identity for the $O(\log ... more >>>

For every $n,s \geq 1$, we construct a matrix tuple $(A_1,\ldots,A_n) \in \mathrm{M}_s(\mathbb{Z})^n$ in deterministic $\mathrm{poly}(n,s)$ time such that every noncommutative polynomial $$f \in \mathbb{C}\langle x_1,x_2,\ldots,x_n\rangle$$ of sparsity at most $s$ satisfies $f = 0$ if and only if $f(A_1,A_2,\ldots,A_n) = 0$. The bit complexity of the entries in ... more >>>