Deterministic Algorithms for Low Individual Degree Factors of Sparse PolynomialsResearch Paper
Factoring multivariate polynomials is a basic task of computer algebra. For polynomials given by circuits or as black boxes it has efficient randomized algorithms (Kaltofen; Kaltofen–Trager), surveyed in §1 of the source, but no deterministic one is known even for sparse polynomials, those with few monomials. Derandomizing factorization is tied to…