Ilya Volkovich

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

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

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