ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > RINGS:
Reports tagged with rings:
TR08-025 | 3rd January 2008
Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2
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 >>>



ISSN 1433-8092 | Imprint