For Toeplitz matrices, there should be FFT methods.

--yes, but I am not sure these available for determinant. I know they work for solving Toeplitz linear systems. (Also, superfast algorithms can in practice be less desirable than mere "fast" algorithms due to complexity of the programming. Depends on your application.)

For circulants := diag(vec(v)) we certainly have det = prod of elements of Fourier transformed vec(v)

The following should be useful: Victor Y. Pan: Structured matrices and polynomials: Unified Superfast Algorithms, Springer-Verlag, (2001) --jj

--Sylvester "resultant" matrices have small "displacement rank." Therefore, superfast algorithms should be available for many operations with this kind of matrix, despite my failure to find a fast algorithm based on Carroll's condensation. I do not have Pan's book but section 5.2 seems (?) to sketch superfast algorithm for computing some kind of representation of a factored form of a structured matrix, which should allow computing its determinant.

Hankel determinants (of Toeplitz matrices) can be evaluated via what Conway & Guy christened the "wall of numbers" in their "Book of Numbers". This algorithm copes with zeros in the table, making it applicable also to finite field computations --- the |F_2 case is particularly simple.

Or at least it would cope, if it weren't for a couple of nasty misprints noticed by Jim Propp; for the correct version see https://cs.uwaterloo.ca/journals/JIS/VOL4/LUNNON/numbwall10.html

That paper also discusses parallel algorithms with time and space complexity of the same order n as the matrix, involving 1-D arrays of finite-state automata.

[ Incidentally, the proof given there is analytical, rather lengthy and delicate. It does at least possess the virtue of presumable correctness.

--that paper is rather immensely long and annoying to read,... but I suspect some of this "number wall" stuff must be equivalent to Carroll condensation applied to Toeplitz matrices, i.e. the latter was already known under other names. Incidentally there are still more names such as "lozenge algorithms" out there.