11
$\begingroup$

I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.

It is known that the determinant of an $n\times n$ matrix can be computed in $\tilde{O}(M(n))$ time, where $M(n)$ is the minimum time required to multiply any two $n\times n$ matrices. It is also known that the best circuit complexity of determinants is polynomial at depth $O(\log^{2}(n))$ and exponential at depth 3. But the circuit complexity of matrix multiplication, for any constant depth, is only polynomial.

Why is there a difference in circuit complexity for determinants and matrix multiplication while it is known that from an algorithm perspective determinant calculation is similar to matrix multiplication? Specifically, why do the circuit complexities have an exponential gap at depth-$3$?

Probably, the explanation is simple but I do not see it. Is there an explanation with 'rigor'?

Also look in: Smallest known formula for the determinant

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Consider circuit value problem and Boolean formula evaluation for various small complexity classes. Deterministic sequential time complexity of them are the similar as far as we know, yet they are very different from circuit complexity perspective. Similarity in one particular type of resource on one model doesn't imply similarity for other resources in other models. One problem can be such that we can exploit parallel computation for one while we can't do that for another one, yet their sequential time complexity can be the same.

When can we expect a more robust relation between the complexity of two problems across models and different resources? When they're are robust reduction between them in both directions that respects resources in those models.

Edit: multiplication has subexponential size depth 3 circuits. Proving a lower-bound of that kind for determinant would show it is not in $\mathsf{NL}$ separating it from $\mathsf{NC^2}$ which is not known.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "multiplication has subexponential size depth 3 circuits." I would think multiplication has $O(n^{3})$ circuit size at any depth since it only involves pulling $n^{2}$ variables and multiplying them in some order and adding the intermediate products. $\endgroup$
    – Turbo
    May 15, 2013 at 19:09
  • 1
    $\begingroup$ Multiplication of two integers is complete for $\mathsf{TC^0}$ and therefore is not in $\mathsf{AC^0}$. $\endgroup$
    – Kaveh
    May 15, 2013 at 19:57
  • $\begingroup$ I am looking at only sequential complexity for now. $\endgroup$
    – Turbo
    May 16, 2013 at 8:52
  • $\begingroup$ I am not sure if I follow your comment. I think my post answers the question in the Boolean setting (the question didn't mention arithmetic circuits originally IIRC). For the arithmetic circuit setting I don't know much, hopefully others will answer the question. $\endgroup$
    – Kaveh
    May 18, 2013 at 11:06
2
$\begingroup$

I'd say that the gap in the arithmetic settings tells us that matrix multiplication is inherently a much more parallel task than the determinant. In other words, while the sequential complexities of both problems are closely related, their parallel complexities are not that close from each other.

A relevant paper is Fast parallel matrix inversion algorithms by Csanky where he proves that the arithmetic complexity $D(n)$ of computing the determinant of an $n\times n$ matrix (that is the depth of an arithmetic circuit computing the determinant) satisfies $$ O(\log n)\le D(n) \le O(\log^2 n).$$ To the best of my knowledge, these are still the best known bounds for this problem. This has to be compared with the trivial depth-$3$ arithmetic circuit computing a matrix multiplication, given by the formula $(A\cdot B)_{ij}=\sum_k A_{ik}B_{kj}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't know if this is an anwser to "why do the circuit complexities have an exponential gap at depth-3?", but at least you have a proof of this fact is Csanky's paper. $\endgroup$
    – Bruno
    May 19, 2013 at 9:57
  • $\begingroup$ If I understand correctly, you are implying: to have a polynomial number of processors, one needs logarithmic depth? $\endgroup$
    – Turbo
    May 19, 2013 at 10:59
  • 1
    $\begingroup$ I didn't remember the exact model Csanky used. Actually, he is considering what we nowadays call arithmetic circuits with bounded fan-in. Thus the lower bound is quite trivial and my comparison with matrix multiplication is not relevant. $\endgroup$
    – Bruno
    May 20, 2013 at 9:11

Your Answer

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

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