__
TR15-042 | 30th March 2015 21:24
__

#### Computations beyond Exponentiation Gates and Applications

**Abstract:**
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 applications, we show that:

\begin{enumerate}

\item A reconstruction algorithm for a circuit class $\mathcal{C}$ can be extended to handle $f^e$ for $f \in \mathcal{C}$.

\item There exists an efficient algorithm for factoring sparse multiquadratic polynomials.

\item There exists an efficient algorithm for testing whether two powers of sparse polynomials are equal.

That is, $f^d \equiv g^e$ when $f$ and $g$ are sparse.

\end{enumerate}