Recent Progress on the Sparse Polynomial Factorization Problem

Polynomial Factorization is the problem of computing the irreducible factors of a given polynomial. Coming up with an efficient deterministic factorization algorithm for sparse polynomials (given as a list of monomials) is a classical open question posed by von zur Gathen and Kaltofen (JCSS 85). Yet, in the last 3 decades the problem has seen only a modest progress. In this talk we survey the previous results and present recent progress in the study of this problem. We also discuss some related problems.

Based on: "Deterministically Factoring Sparse Polynomials into Multilinear Factors" and "Computations beyond Exponentiation Gates and Applications".