Determinant of a polynomial matrix A matrix determinant (naively) can be computed in $O(n!)$ steps, or with a proper LU decomposition $O(n^3)$ steps. This assumes that all the matrix elements are constant. If, however the matrix elements are polynomials (say univariate of max order $p$) at each step of the LU decomposition an element is multiplied by another element producing (on average) ever larger polynomials. Each step therefore takes longer and longer - is the cost perform the decomposition still a polynomial?
EDIT: To clarify my reasoning a bit, if polynomial (using FFT as J.M. suggests in the comments) takes $O(m \log m)$, and we must perform $O(n^3)$ operations to get the LU decomposition, each step the polynomial could effectively double in degree at each multiplication*. The running time would look something like
$$ \approx O \left ( \sum_{k}^{n^3} (p \ln p)^{2k} \right ) .$$
* (it doesn't quite do that, and this is where I'm stuck)
 A: Suppose each entry of your $n \times n$ matrix is a polynomial of degree $d$ in the variable $t$. Appealing to the cofactor expansion, we see that the determinant will be a polynomial in $t$ of degree at most $dn$; lets call it $D(t)$. So you can do the following: evaluate the determinant at $t=1,2, \ldots, dn$. You will thus know $D(1),D(2),\ldots,D(dn)$ and can find out the coefficients of $D$ by interpolation.
This involves:
(i) $dn$ determinant evaluations, each of which takes $O(n^3)$ operations.
(ii) Interpolating a polynomial of degree $dn$. This can be done by solving a $dn \times dn$ system of equations (see https://en.wikipedia.org/wiki/Polynomial_interpolation under "Constructing the interpolating polynomial"). There are algorithms which will do this in $O(dn \log^2 dn)$.
Your final number of operations will be $O(d n^4 + dn \log^2 dn)$.
I would be interested in knowing if its possible to do this faster.
Update: I corrected an error and incorporated a suggestion of J.M. in the comments.
