On Efficient Noncommutative Polynomial Factorization via Higman Linearization

V. Arvind, Pushkar S. Joglekar

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x1,x2,...,xn over the field F.…