# Smallest known formula for the determinant

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?

-

 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