Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 12 down vote favorite
1

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 Super-Polynomial Size).

Do you have any reference for this? In particular, what is this formula?

share|improve this question

1 Answer

up vote 12 down vote accepted

One way is described in Berkowitz, On computing the determinant in small parallel time using a small number of processors (see also Soltys, Berkowitz's algorithm and clow sequences). Another way is described in Hrubeš and Tzameret, Short proofs for the determinant identities.

share|improve this answer
Thanks Yuval. I could have thought a bit more to my question since I knew Berkowitz's algorithm... By the way, I did not know Soltys' paper, thus thanks for the pointer! – Bruno Aug 31 '12 at 12:31
Note that in our paper it is not a direct construction of a quasipolynomial formula for the determinant, but rather a simple recursive construction of a polynomial-size arithmetic circuit with division gates for the determinant. This then results in an $NC^2$-circuit (and quasipolynomial size formula) only after using elimination of division gates and balancing the circuit to have $\log^2(n)$ depth. – Iddo Tzameret Feb 22 at 8:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.