Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MULTIVARIATE POLYNOMIAL FACTORIZATION:
Reports tagged with Multivariate Polynomial Factorization:
TR15-042 | 30th March 2015
Ilya Volkovich

#### Computations beyond Exponentiation Gates and Applications

In Arithmetic Circuit Complexity the standard operations are $\{+,\times\}$.
Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}).
In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power.
That is, beyond an exponentiation gate. As ... more >>>

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

TR22-070 | 8th May 2022
Pranav Bisht, Ilya Volkovich

#### On Solving Sparse Polynomial Factorization Related Problems

Revisions: 6

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most \$s^{O(d^2\log ... more >>>

ISSN 1433-8092 | Imprint