TY - GEN

T1 - Deterministic factorization of sparse polynomials with bounded individual degree

AU - Bhargava, Vishwas

AU - Saraf, Shubhangi

AU - Volkovich, Ilya

N1 - Publisher Copyright:
© 2018 IEEE.

PY - 2018/11/30

Y1 - 2018/11/30

N2 - 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.

AB - 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.

KW - Bounds on factor sparsity

KW - Multivariate polynomial factorization

KW - Sparse polynomials

UR - http://www.scopus.com/inward/record.url?scp=85059807595&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059807595&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2018.00053

DO - 10.1109/FOCS.2018.00053

M3 - Conference contribution

AN - SCOPUS:85059807595

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 485

EP - 496

BT - Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

A2 - Thorup, Mikkel

PB - IEEE Computer Society

T2 - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

Y2 - 7 October 2018 through 9 October 2018

ER -