New results on Noncommutative and Commutative Polynomial Identity Testing

V. 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 stu…