Questions tagged [determinant]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
22
votes
2answers
1k views

Lower bound for determinant and permanent

In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
13
votes
1answer
802 views

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-...