# 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 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?

• in some intuitive sense, without cancelations the determinant is the same thing as the permanent – Sasho Nikolov May 3 '13 at 23:44

• 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 May 10 '13 at 4:21
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)$.