<p>The best circuit known for determinants of size $n \times n$ have size $n^{O(log(n))}$. Is there any evidence either way that this can be brought to fully polynomial size or not? I am aware of Raz's work that this is lower bound for multilinear circuits.</p>

CC BY-SA 3.0
2013-05-12T12:42:01.470Z
The best known arithmetic circuit for $n \times n$ determinant has size $\tilde{O}(n^{\omega})$ (where $\omega < 2.373$ is the matrix multiplication exponent)
Ryan Williams
CC BY-SA 4.0
2023-08-04T04:56:23.370Z
Maybe the question was meant to be about formula size rather than circuit size? Best known formula size for the determinant is quasipolynomial. But improving this to polynomial or proving a matching lower bound is a well-known open question.
Joshua Grochow
<arithmetic-circuits>
Determinant complexity
Turbo
# Determinant complexity

(Asked by: username_0 on 2013-05-12)

The best circuit known for determinants of size $n \times n$ have size $n^{O(log(n))}$. Is there any evidence either way that this can be brought to fully polynomial size or not? I am aware of Raz's work that this is lower bound for multilinear circuits.

**Tags:** arithmetic-circuits

> **Comments:**
> **username_1**: The best known arithmetic circuit for $n \times n$ determinant has size $\tilde{O}(n^{\omega})$ (where $\omega < 2.373$ is the matrix multiplication exponent)  
> **username_2**: Maybe the question was meant to be about formula size rather than circuit size? Best known formula size for the determinant is quasipolynomial. But improving this to polynomial or proving a matching lower bound is a well-known open question.  

---

## 0 answers

