Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

In this article, we study the problem of deterministic factorization of sparse polynomials. We show that if f F[x1,x2,..,xn] is a polynomial with s monomials, with individual degrees of its variables bounded by d, then f can be deterministically factored in time spoly(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 languageEnglish (US)
Article number8
JournalJournal of the ACM
Volume67
Issue number2
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree'. Together they form a unique fingerprint.

Cite this