Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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