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 essential for attaining a circuit of polynomial size with logarithmic or linear depth to calculate determinant (and any possible best circuit for permanent)? Are there fully exponential (not just superpolynomial or sub exponential) lower bounds for these problems using circuits without cancellation?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ in some intuitive sense, without cancelations the determinant is the same thing as the permanent $\endgroup$– Sasho NikolovCommented May 3, 2013 at 23:44
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Yes, cancellations are needed and there are lower bounds for monotone and for non-commutative models where cancellations are impossible. See discussion in Monotone arithmetic circuits. A survey of aritmetic circuit complexity can be found in http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf
-
1$\begingroup$ JIC someone has an issue that monotone circuits (no -ve constants) cannot compute the determinant trivially (as it contains -ve coefs). Define formal monomials inductively as follows: If $f = g_1 + g_2$, then the formal monomials of $f$ is the union of that of $g_1$ and $g_2$. If $f = g_1 \times g_2$, then the formal monomials are all monomials obtained by taking one of $g_1$ and multiplying by one of $g_2$. Jerrum-Snir's lower bound works as long as the circuit satisfies the property that the formal monomials of the root is equal to the non-zero monomials of the polynomial computed. $\endgroup$ Commented May 10, 2013 at 4:21
$\begingroup$
$\endgroup$
I think this paper directly answers your question.
Cancellation is exponentially powerful for computing the determinant
Sengupta shows that even if you use subtraction (hence the circuit is not monotone) but as long as you never "cancel" any computed monomials, then the circuit computing determinant of the matrix of size $n \times n$ has size at least $n(2^{n-1}-1)$.
