<p>One way is described in Berkowitz, <a href="http://www.sciencedirect.com/science/article/pii/0020019084900188"><em>On computing the determinant in small parallel time using a small number of processors</em></a> (see also Soltys, <a href="http://arxiv.org/pdf/math/0201315"><em>Berkowitz's algorithm and clow sequences</em></a>). Another way is described in Hrubeš and Tzameret, <a href="http://arxiv.org/pdf/1112.6265"><em>Short proofs for the determinant identities</em></a>.</p>

CC BY-SA 3.0
2012-08-31T12:31:12.280Z
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
CC BY-SA 3.0
2013-02-22T08:28:32.697Z
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
CC BY-SA 3.0
2012-08-30T21:18:41.497Z
2013-02-15T05:42:13.583Z
2013-02-15T05:42:13.583Z
Yuval Filmus
<p>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 <em><a href="http://eccc.hpi-web.de/report/2003/067/">Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size</a></em>). </p>

<p>Do you have any reference for this? In particular, what is this formula?</p>

<cc.complexity-theory><reference-request><algebraic-complexity><determinant>
Smallest known formula for the determinant
Bruno
# Smallest known formula for the determinant

(Asked by: username_0 on 2012-08-30)

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](http://eccc.hpi-web.de/report/2003/067/)*).

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

**Tags:** cc.complexity-theory, reference-request, algebraic-complexity, determinant

---

## 1 answers

### Answer by username_1 on 2012-08-30. Score: 13 | Accepted answer

One way is described in Berkowitz, [*On computing the determinant in small parallel time using a small number of processors*](http://www.sciencedirect.com/science/article/pii/0020019084900188) (see also Soltys, [*Berkowitz's algorithm and clow sequences*](http://arxiv.org/pdf/math/0201315)). Another way is described in Hrubeš and Tzameret, [*Short proofs for the determinant identities*](http://arxiv.org/pdf/1112.6265).

> **Comments:**
> **username_0**: 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!  
> **username_2**: 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.  

---

