Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

We study the problem of deterministic factorization of sparse polynomials. We show that if f \in \F[x1,…,xn] is a polynomial with s monomials, with individual degrees of its variables bounded by d, then f can be deterministically factored in time s^{O(\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(d^2 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.

This is joint work with Shubhangi Saraf and Ilya Volkovich.