# Implications of approximating the determinant

It is known that one can compute exactly the determinant of an $n\times n$ matrix in determinstic $\log^2(n)$ space. What would be the complexity implications of approximating the determinant of a real matrix, of norm at most $1$ ($\left\|A\right\|\leq 1$) in randomized logarithmic space, up to say, a $1/\text{poly}$ accuracy?

In this respect, what would be the "correct" approximation to ask for - multiplicative or additive? (see one of the answers below).

• Are these supposed to be on a Real RAM? $\:$ – user6973 May 2 '13 at 19:03
• I'm not sure I properly understand the question, but if you refer to the precision of the arithmetic, then I'd assume that each real number is stored in log(n) bits. – Lior Eldar May 3 '13 at 13:10

• Hi Peter Taylor, I think that to speak of, say 0.5 precision you first need somehow to specify the largest operator norm you support. So for example if your input $A$ has $\left\|A\right\|\leq 1$, then your determinant additive error can be $1/poly(n)$. So even if your input is given to you as truncated integers, each of $log(n)$ bits, then the maximal norm for which you are required to approximate the determinant would be $n^n$ in terms of integers, meaning that $0.5$ approximation error is much smaller than $1/poly(n)$ relative to $\left\|A\right\|$. – Lior Eldar May 7 '13 at 13:51
• I think the trouble with additive error relative to the norm is that it doesn't really scale nicely. Say I had an algorithm that gave a $1/poly(n)$ approximation error relative to $||A||$. Now let $A'$ be the $n^3 \times n^3$ block diagonal matrix formed using $n^2$ copies of $A$ as blocks. Then $||A||=||A'||$, but $\det(A')=\det(A)^{n^2}$, so a $||A'||/poly(n)$ additive error for $det(A')$ scales to a $O(1)$ additive error for $det (A)$. – Kevin Costello May 10 '13 at 19:43