I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits.I would like to know what is the state-of-the-art bit-complexity.As far as I could find, the two possible candidates are:(1) The low-depth circuits, due to Csansky [1976], and Berkowitz [1984], but these, despite having $log^2(n)$ depth, require some $n^4$ bit operations.(2) The Bunch and Hopcroft [1974] algorithm, which takes any black-box algorithm for integer matrix multiplication, and produces an algorithm for the determinant using the same $\textbf{arithmetic}$ complexity.  Since any two $M$-bit integers can be multiplied in $M \cdot log^2(M)$ operations, and the largest value during the computation can be as large as $2^{M n}$, it seems that its bit-complexity is $\tilde{O}(M n^{\omega+1})$, where $\omega$ is the state-of-the-art matrix product coefficient $< 2.38$.Is there a better upper-bound?
state-of-the-art bit complexity of the determinant
time complexity;linear algebra;matrix product;space complexity;determinant
Storjohann designs a Las-Vegas algorithm with $\tilde O(n^\omega M)$ bit operationshttp://dx.doi.org/10.1016/j.jco.2005.04.002Prior to this, Kaltofen and Villard gave improved algorithms, see http://lara.inist.fr/bitstream/handle/2332/850/LIP-RR2003-36.pdf%3Fsequence%3D1