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?
Cancellation and determinant
circuit complexity;algebraic complexity;permanent;arithmetic circuits;determinant