Deterministic factorization of sparse polynomials with bounded individual degree

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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)logn . 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 Carathéodory'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.

Original languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages485-496
Number of pages12
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October
ISSN (Print)0272-5428

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Country/TerritoryFrance
CityParis
Period10/7/1810/9/18

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

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