Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-042 | 30th March 2015 21:24

#### Computations beyond Exponentiation Gates and Applications

TR15-042
Authors: Ilya Volkovich
Publication: 31st March 2015 04:05
Keywords:

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}

ISSN 1433-8092 | Imprint