Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ARITHMETIC CIRCUITS:
Reports tagged with Arithmetic Circuits:
TR22-022 | 18th February 2022
Vikraman Arvind, Pushkar Joglekar

#### On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Revisions: 3

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

TR22-042 | 31st March 2022
Vikraman Arvind, Pushkar Joglekar

#### Matrix Polynomial Factorization via Higman Linearization

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

ISSN 1433-8092 | Imprint