Lower bound for determinant and permanent

Question

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 following questions : Grigoriev and Karpinski proved an $2^{\Omega{(n)}}$ lower bound for any depth-3 arithmetic circuit computing the Determinant of $n \times n$ matrices over finite fields (which I guess, also holds for the Permanent). Ryser's formula for computing the Permanent gives a depth-3 arithmetic circuit of size $O(n^2 2^n) = 2^{O(n)}$. This shows that the result is essentially tight for depth-3 circuits for the Permanent over finite fields. I have two questions:

1) Is there a depth-3 formula for the determinant analogous to Ryser's formula for the Permanent?

2) Does a lower bound on the size of arithmetic circuits computing the Determinant polynomial \textit{always} yield a lower bound for the Permanent polynomial?(Over $\mathbb{F}_2$ they are the same polynomials).

Though my question currenly is regarding these polynomials over finite fields, I would also like to know the status of these questions over arbitrary fields.

Answer 1

Permanent is complete for VNP under p-projections over any field not of characteristic 2. This provides a positive answer to your second question. If this reduction were linear, it would give a positive answer to your first question, but I believe that remains open.

In more detail: there is some polynomial $q(n)$ such that $det_n(X)$ is a projection of $perm_{q(n)}(Y)$, i.e. there is a certain substitution sending each variable $y_{ij}$ either to a variable $x_{k\ell}$ or a constant such that after this substitution the $q(n) \times q(n)$ permanent is computing the $n \times n$ determinant.

1) Thus Ryser's formula yields a depth 3 formula (depth does not increase under projections because the substitutions can be done on the input gates) of size $2^{O(q(n))}$ for determinant. UPDATE: As @Ramprasad points out in the comments, this only gives something nontrivial if $q(n) = o(n \log n)$, since there is a trivial depth 2 formula of size $n \cdot n! = 2^{O(n \log n)}$ for det. I am with Ramprasad in that the best I know is the reduction through ABPs, which yields $q(n)=O(n^3)$.

2) If the $m \times m$ permanent can be computed - again, over some field of characteristic not 2 - by a circuit of size $s(m)$, then $n \times n$ determinant can be computed by a circuit of size $s(q(n))$. So a lower bound of $b(n)$ on circuit-size for $det_n$ yields a lower bound of $b(q^{-1}(n))$ on circuit-size for the permanent (that's $q$ inverse, not $1/q(n)$). The above-mentioned $q(n)=O(n^3)$ yields a $b(n^{1/3})$ perm lower bound from a $b(n)$ det lower bound.

Answer 2

It is very possible that the determinant is, in a way, harder than the permanent. They are both polynomials, the Waring Rank(sums of n powers of linear forms) of the permanent is roughly 4^n, Chow Rank(sums of products of linear forms) is roughly 2^n. Clearly, Waring Rank \leq 2^{n-1} Chow Rank. For the determinant, those numbers are just lower bounds. On the other hand, I proved a while ago that the Waring rank of the determinant is upper bounded by (n+1)! and this might be close to the truth.