## Abstract

In this article, we study the problem of deterministic factorization of sparse polynomials. We show that if f F[x_{1},x_{2},..,x_{n}] is a 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 that 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^{(9 d2 log n)}. This is the first non-trivial 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 Carathéodory's Theorem. Our work addresses and partially answers a question of von zur Gathen and Kaltofen [1985] who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials.

Original language | English (US) |
---|---|

Article number | 8 |

Journal | Journal of the ACM |

Volume | 67 |

Issue number | 2 |

DOIs | |

State | Published - May 4 2020 |

## All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence

## Keywords

- Bounds on factor sparsity
- multivariate polynomial factorization
- sparse polynomials