Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if f is an n-variate polynomial with s monomials, with individual degrees of its variables bounded by d, then f can be deterministically factored in time s poly(d) log n. Prior to our work, the only efficient factoring algorithms known for this class of polynomials were randomized, and other than for the cases of d = 1 and d = 2, only exponential time deterministic factoring algorithms were known. A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular we show if f is an s-sparse polynomial in n variables, with individual degrees of its variables bounded by d, then the sparsity of each factor of f is bounded by s O(d2 log n). This is the first nontrivial bound on factor sparsity for d > 2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem. Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials.

Authors

• Vishwas Bhargava
• Shubhangi Saraf
• Ilya Volkovich

Keywords

• Geometry
• Computer science
• Testing
• Complexity theory
• Runtime
• Approximation algorithms
• Deterministic
• Polynomial Factor
• Sparse Polynomial
• Sparsity
• Crucial Ingredient
• Carathéodory
• Lower Bound
• Efficient Algorithm
• General Case
• Finite Set
• Natural Question
• Convex Hull
• Characteristic Zero
• Polynomial Of Degree
• Divisible
• Convex Combination
• Basic Facts
• Input Point
• Corner Points
• Fundamental Results
• Monic Polynomial
• General Polynomial
• Minkowski Sum
• Bounds on Factor Sparsity
• Multivariate Polynomial Factorization
• Sparse polynomials