IMSc Webinar

On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Pushkar Joglekar

Vishwakarma Institute of Technology, Pune

Join the seminar at this link: zoom.us/j/99018916192 .
Meeting ID: 990 1891 6192

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring $\F\angle{x_1,x_2,\ldots,x_n}$ of polynomials in noncommuting variables $x_1,x_2,\ldots,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\angle{x_1,x_2,\ldots,x_n}$ as input, where $\F=\F_q$ is a finite field, we give a randomized algorithm that runs in time polynomial in $s, n$ and $\log_2 q$ that computes a factorization of $f$ as a product $f=f_1 f_2 \cdots f_r$, where each $f_i$ is an irreducible polynomial that is output as a noncommutative algebraic branching program.

The algorithm works by first transforming $f$ into a linear matrix $L$ using Higman's linearization of polynomials. We then factorize the linear matrix $L$ and recover the factorization of $f$. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.

Joint work with V Arvind; to appear in CCC 2022.