Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-042 | 30th March 2015 21:24

Computations beyond Exponentiation Gates and Applications

RSS-Feed




TR15-042
Authors: Ilya Volkovich
Publication: 31st March 2015 04:05
Downloads: 1399
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