We consider the problem of determining whether a t-sparse or
lacunary polynomial f is a perfect power, that is, f=h^{r} for
some other polynomial h and integer r, and of finding h and r
should they exist. We show how to determine if f is a perfect
power in time polynomial in t and log(deg(f)), i.e., polynomial
in the size of the lacunary representation. The algorithm works over
GF(q)[x] (at least for large characteristic) and over Z[x],
where the cost is also polynomial in log(||f||). Subject to a
conjecture, we show how to find h if it exists via a kind of
sparse Newton iteration, again in time polynomial in the size of the
sparse representation. Finally, we demonstrate an implementation using
the C++ library NTL.