  New algorithms are presented for computing annihilating polynomials of
Toeplitz, Hankel, and more generally Toeplitz+ Hankel-like matrices over a
field. Our approach follows works on Coppersmith's block Wiedemann method with
structured projections, which have been recently successfully applied for
computing the bivariate resultant. A first baby-step/giant step approach --
directly derived using known techniques on structured matrices -- gives a
randomized Monte Carlo algorithm for the minimal polynomial of an $n\times n$
Toeplitz or Hankel-like matrix of displacement rank $\alpha$ using $\tilde
O(n^{\omega - c(\omega)} \alpha^{c(\omega)})$ arithmetic operations, where
$\omega$ is the exponent of matrix multiplication and $c(2.373)\approx 0.523$
for the best known value of $\omega$. For generic Toeplitz+Hankel-like matrices
a second algorithm computes the characteristic polynomial in $\tilde
O(n^{2-1/\omega})$ operations when the displacement rank is considered
constant. Previous algorithms required $O(n^2)$ operations while the exponents
presented here are respectively less than $1.86$ and $1.58$ with the best known
estimate for $\omega$.
