<p>Yes, cancellations are needed and there are lower bounds for monotone and for non-commutative models where cancellations are impossible.  See discussion in <a href="https://cstheory.stackexchange.com/questions/8918/monotone-arithmetic-circuits">Monotone arithmetic circuits</a>.  A survey of aritmetic circuit complexity can be found in <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" rel="nofollow noreferrer">http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf</a></p>

CC BY-SA 3.0
2013-05-10T04:21:26.400Z
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.
Ramprasad
CC BY-SA 3.0
2013-05-03T22:53:00.397Z
2013-05-03T23:00:17.680Z
2017-04-13T12:32:28.053Z
Noam
<p>I think this paper directly answers your question.</p>

<blockquote>
  <p><a href="http://www.sciencedirect.com/science/article/pii/S0020019097000690" rel="nofollow">Cancellation is exponentially powerful for computing the determinant</a></p>
</blockquote>

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

CC BY-SA 3.0
2013-05-09T20:32:15.060Z
2013-05-10T00:41:40.593Z
2013-05-10T00:41:40.593Z
Thatchaphol
<p>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?</p>

CC BY-SA 3.0
2013-05-03T23:44:30.603Z
in some intuitive sense, without cancelations the determinant is the same thing as the permanent
Sasho Nikolov
<circuit-complexity><algebraic-complexity><permanent><arithmetic-circuits><determinant>
Cancellation and determinant
Turbo
# Cancellation and determinant

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

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?

**Tags:** circuit-complexity, algebraic-complexity, permanent, arithmetic-circuits, determinant
> **Comments:**
> **username_1**: in some intuitive sense, without cancelations the determinant is the same thing as the permanent  

---

## 2 answers

### Answer by username_2 on 2013-05-03. Score: 11

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](https://cstheory.stackexchange.com/questions/8918/monotone-arithmetic-circuits). A survey of aritmetic circuit complexity can be found in <http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf>

> **Comments:**
> **username_3**: 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.  

---

### Answer by username_4 on 2013-05-09. Score: 1

I think this paper directly answers your question.

> [Cancellation is exponentially powerful for computing the determinant](http://www.sciencedirect.com/science/article/pii/S0020019097000690)

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


---

