The determinant tag has no wiki summary.
8
votes
1answer
119 views
Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size
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 ...
7
votes
2answers
290 views
Cancellation and determinant
Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation ...
15
votes
1answer
326 views
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 ...
7
votes
0answers
127 views
Grigoriev-Karpinski for the permanent
Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the ...
7
votes
0answers
119 views
Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)
I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ ...
18
votes
2answers
516 views
Lower bound for determinant and permanent
In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
12
votes
1answer
359 views
Smallest known formula for the determinant
The smallest known formula for the determinant has size $n^{\mathcal O(\log n)}$ according to the folklore (or to Ran Raz in its paper Multi-Linear Formulas for Permanent and Determinant are of ...
12
votes
2answers
488 views
Gaussian Elimination in terms of Group Action
Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to ...
