The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question continues to remain open, we make some progress towards its resolution. To that effect, ... 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 >>>