Vikraman Arvind, Pushkar Joglekar

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:

Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>>

Vikraman Arvind, Pushkar Joglekar

In continuation to our recent work on noncommutative

polynomial factorization, we consider the factorization problem for

matrices of polynomials and show the following results.

\begin{itemize}

\item Given as input a full rank $d\times d$ matrix $M$ whose entries

$M_{ij}$ are polynomials in the free noncommutative ring

more >>>