<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-05-15T19:09:34.610Z
"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.
Turbo
CC BY-SA 3.0
2013-05-15T19:57:03.167Z
Multiplication of two integers is complete for $\mathsf{TC^0}$ and therefore is not in $\mathsf{AC^0}$.
Kaveh
CC BY-SA 3.0
2013-05-16T08:52:17.757Z
I am looking at only sequential complexity for now.
Turbo
CC BY-SA 3.0
2013-05-18T11:06:28.840Z
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.
Kaveh
CC BY-SA 3.0
2013-05-15T17:53:01.133Z
2013-05-15T18:03:21.750Z
2013-05-15T18:03:21.750Z
Kaveh
<p>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.</p>

<p>A relevant paper is <a href="http://www.mathcs.emory.edu/~cs526000/share/0320/csanky-determinant.pdf" rel="nofollow"><em>Fast parallel matrix inversion algorithms</em></a> 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}$. </p>

CC BY-SA 3.0
2013-05-19T09:57:39.070Z
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.
Bruno
CC BY-SA 3.0
2013-05-19T10:59:12.347Z
If I understand correctly, you are implying: to have a polynomial number of processors, one needs logarithmic depth?
Turbo
CC BY-SA 3.0
2013-05-20T09:11:31.673Z
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.
Bruno
CC BY-SA 3.0
2013-05-19T09:53:39.020Z
2013-05-19T09:53:39.020Z
Bruno
<p>I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.</p>

<p>It is known that the determinant of an $n\times n$ matrix can be <a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra" rel="nofollow noreferrer">computed</a> 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 <a href="http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Upper_bounds" rel="nofollow noreferrer">polynomial</a> at depth $O(\log^{2}(n))$ and <a href="http://people.cs.uchicago.edu/~razborov/files/depth3.ps" rel="nofollow noreferrer">exponential</a> at depth 3.  But the circuit complexity of matrix multiplication, for any constant depth, is only polynomial.</p>

<p>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 <a href="http://www4.ncsu.edu/~kaltofen/bibliography/04/KaVi04_2697263.pdf" rel="nofollow noreferrer">similar</a> to matrix multiplication? Specifically, why do the circuit complexities have an exponential gap at depth-$3$? </p>

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

<p>Also look in: <a href="https://cstheory.stackexchange.com/questions/12448/smallest-known-formula-for-the-determinant">Smallest known formula for the determinant</a></p>

<algebraic-complexity><arithmetic-circuits><matrix-product><determinant>
Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size
Turbo
# Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size

(Asked by: username_0 on 2013-05-15)

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](http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra) 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](http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Upper_bounds) at depth $O(\log^{2}(n))$ and [exponential](http://people.cs.uchicago.edu/~razborov/files/depth3.ps) 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](http://www4.ncsu.edu/~kaltofen/bibliography/04/KaVi04_2697263.pdf) 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](https://cstheory.stackexchange.com/questions/12448/smallest-known-formula-for-the-determinant)

**Tags:** algebraic-complexity, arithmetic-circuits, matrix-product, determinant

---

## 2 answers

### Answer by username_1 on 2013-05-15. Score: 3

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.

> **Comments:**
> **username_0**: "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.  
> **username_1**: Multiplication of two integers is complete for $\mathsf{TC^0}$ and therefore is not in $\mathsf{AC^0}$.  
> **username_0**: I am looking at only sequential complexity for now.  
> **username_1**: 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.  

---

### Answer by username_2 on 2013-05-19. Score: 2

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*](http://www.mathcs.emory.edu/~cs526000/share/0320/csanky-determinant.pdf) 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}$.

> **Comments:**
> **username_2**: 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.  
> **username_0**: If I understand correctly, you are implying: to have a polynomial number of processors, one needs logarithmic depth?  
> **username_2**: 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.  

---

