Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

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