# state-of-the-art bit complexity of the determinant

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?

## 1 Answer

Storjohann designs a Las-Vegas algorithm with $\tilde O(n^\omega M)$ bit operations http://dx.doi.org/10.1016/j.jco.2005.04.002

Prior to this, Kaltofen and Villard gave improved algorithms, see http://lara.inist.fr/bitstream/handle/2332/850/LIP-RR2003-36.pdf%3Fsequence%3D1

• Thanks for the great links! However, I do not understand the bound you are stating: it says in the paper, that the bit complexity is $\tilde{O}(n^{\omega} log (\left\|A\right\|))$, so if $A$ is an $n\times n$ matrix of $M$ bits each, then $\left\|A\right\|$ can be as large as $2^{Mn}$, so its complexity is exactly $\tilde{O}(n^{\omega+1} M)$. What am I missing here? – Lior Eldar Jun 19 '13 at 7:03
• $|| A ||$ is the max-norm in Storjohann's paper, so $||A|| \le 2^M$. – Markus Bläser Jun 19 '13 at 8:04