Using ideas from automata theory we design a new efficient (deterministic) identity test for the \emph{noncommutative} polynomial identity testing problem (first introduced and studied by Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely, given as input a noncommutative circuit $C(x_1,\cdots,x_n)$ computing a polynomial in $\F\{x_1,\cdots,x_n\}$ of degree $d$ with ...
more >>>