Complexity of determinant of k-minors Let $A$ be an $n \times n$-matrix, and let $1 \leq k \leq n$. Which algorithms do exist, or what is know about the complexity of computing determinants of all $k \times k$-minors?

The naive algorithm has complexity $\Theta( {n \choose k}^2 k! )$. If we apply Gaussian elemination for each minor $\Theta( {n \choose k}^2 k^3 )$. Of course, there is a dynamic programming approach, too, but I am not firm enough to compute its complexity.

I am also interested whether there is a lower bound actually known.
Not quite answering what you want, but if you want the gcd of all $k\times k$ minors, then you can compute it in $O(n^\omega)$ or up to logarithmic factors. This is known as Smith Normal Form. For any matrix over principal ideal ring (or PID), the $k$ invariant factor of Smith normal form is the ${\rm gcd}$ of all $k\times k$ minors.