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

• That's interesting.... recently (eccc.hpi-web.de/report/2013/026) a $2^{O(n^{1/2}\log n})$ upper bound has been proved over the complex numbers. So there is somehow a huge difference in characteristic zero and finite fields... – Ryan Williams Feb 15 '13 at 0:05
• I should have mentioned the new result. I was reading the paper and I wanted to know what can be inferred from known results for the finite field case. Will update the question to include the paper. – Nikhil Feb 15 '13 at 4:01
• Are there similar/any lower bound known for determinant/permanent in case of depth 3 circuits over fields of characteristic zero? – Gorav Jindal Jun 5 '14 at 15:31
• Over characteristic zero, AFAIK, the best lower bound is $\Omega(n^2)$ for the elementary symmetric function(and also the determinant polynomial) due to Shpilka and Wigderson. Check cs.technion.ac.il/~shpilka/publications/… – Nikhil Jun 8 '14 at 8:33

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.

• Just want to point out that the determinant being a projection of a polynomially larger permanent doesn't quite yield much. The determinant of course has a trivial $n!$ sized circuit. So even showing that the $n\times n$ determinant is a projection of a $n^2\times n^2$ permanent does not yield anything non-trivial via Ryser's formula. I guess, for your proof strategy, one needs to show that the $q(n) = O(n)$, but I don't see how to get this from the usual reduction. AFAIK, no depth-3 circuit asymptotically smaller than $n!$ is known for the determinant over finite fields. – Ramprasad Feb 15 '13 at 5:58
• @Ramprasad: There is a projection of $DET_n$ to $PERM_{O(n)}$ in the general case over arbitrary fields right? So implementing this reduction in depth-3 is the hurdle - is that what you mean? – Nikhil Feb 15 '13 at 11:18
• @Nikhil: Is there such a projection?! If that were true, then of course we would immediately have a $2^{O(n)}$ depth-3 circuit for the determinant by just using Ryser's formula (which wasn't known prior to the chasm-at-depth-3 result). The only reduction I know is to take the ABP for the determinant (whcih is $O(n^3)$-sized) and write that as a projection of a $O(n^3)$ sized permanent. I would be very surprised of a reduction to $O(n)$-sized permanent holds. – Ramprasad Feb 15 '13 at 11:30
• I'm fairly sure that is a typo/error in the article (but I shall check with Manindra though). Avi Wigderson's talk (PPT) during Valiant's 60th birthday celebrations is one of the places where it was stated that improving $n!$ for the depth-3 complexity of determinant was unknown. Depth-3 circuits over finite fields is a curious example where the best upper bound for the permanent is smaller than the determinant! – Ramprasad Feb 15 '13 at 14:49
• – Ramprasad Feb 15 '13 at 15:26

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.

• I removed the advertisement. – Jeffε Feb 16 '13 at 16:55
• Can you give the reference for the proof? – Kaveh Feb 17 '13 at 1:10