Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOUNDS ON FACTOR SPARSITY:
Reports tagged with Bounds on Factor Sparsity:
TR18-130 | 16th July 2018
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

#### Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,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 ... more >>>

ISSN 1433-8092 | Imprint