16
$\begingroup$

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).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are these supposed to be on a Real RAM? $\:$ $\endgroup$
    – user6973
    Commented May 2, 2013 at 19:03
  • $\begingroup$ 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. $\endgroup$
    – Lior Eldar
    Commented May 3, 2013 at 13:10

1 Answer 1

Reset to default
4
+50
$\begingroup$

With a risk of not having understood the details of the question properly: Being able to approximate the determinant within any factor requires being able to decide whether a square matrix is singular or not, which should have some consequences.

For one thing, it gives a randomized test for whether a general graph has a perfect matching (via the Tutte matrix and Schwarz-Zippel). I don't think the latter is known in randomized logspace (e.g., the Complexity Zoo lists bipartite perfect matching as hard for NL).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks Magnus, though I was actually thinking of an additive approximation error, in which case you won't be required to tell apart whether a matrix is singular or not. Multilipcative approximation may also be of interest, so right now, I'm not sure what's the best definition. $\endgroup$
    – Lior Eldar
    Commented May 3, 2013 at 13:07
  • 1
    $\begingroup$ @LiorEldar, surely even with additive approximation error, if the entries in the matrix are integers and the additive error bound is less than 0.5 you have a foolproof singularity test? $\endgroup$
    – Peter Taylor
    Commented May 6, 2013 at 16:58
  • $\begingroup$ 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\|$. $\endgroup$
    – Lior Eldar
    Commented May 7, 2013 at 13:51
  • $\begingroup$ 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)$. $\endgroup$
    – Kevin Costello
    Commented May 10, 2013 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.