Name
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
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">poly(d) log n</sup>
. 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
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(d2 log n)</sup>
. 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/FOCS.2018.00053 | 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | Volume |
Bounds on Factor Sparsity,Multivariate Polynomial Factorization,Sparse polynomials | Journal | 25 |
ISSN | ISBN | Citations |
1523-8288 | 978-1-5386-4231-3 | 0 |
PageRank | References | Authors |
0.34 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vishwas Bhargava | 1 | 1 | 3.18 |
| Shubhangi Saraf | 2 | 263 | 24.55 |
| Ilya Volkovich | 3 | 6 | 4.42 |