Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > POLYNOMIAL FACTORIZATION, NON-COMMUTATIVE ARITHMETIC CIRCUITS:
Reports tagged with polynomial factorization, non-commutative arithmetic circuits:
TR15-004 | 4th January 2015
Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan

#### On the Complexity of Noncommutative Polynomial Factorization

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\ldots,x_n\rangle$ of polynomials over the field $\mathbb{F}$ and noncommuting variables $x_1,x_2,\ldots,x_n$. Our main results are the following.

Although $\mathbb{F}\langle x_1,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in ... more >>>

ISSN 1433-8092 | Imprint