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

CC BY-SA 3.0
2013-02-16T16:55:07.683Z
I removed the advertisement.
Jeffε
CC BY-SA 3.0
2013-02-17T01:10:28.323Z
Can you give the reference for the proof?
Kaveh
CC BY-SA 3.0
2013-02-16T14:41:35.037Z
2013-02-16T16:54:56.857Z
2013-02-16T16:54:56.857Z
Leonid Gurvits
<p>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.</p>

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

<p>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.   <strong>UPDATE</strong>: 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)$. </p>

<p>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$ <em>inverse</em>, 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.</p>

CC BY-SA 3.0
2013-02-15T05:58:48.260Z
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
CC BY-SA 3.0
2013-02-15T11:18:32.573Z
@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
CC BY-SA 3.0
2013-02-15T11:30:28.783Z
@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
CC BY-SA 3.0
2013-02-15T11:43:56.397Z
@Ramprasad: I think I am definitely missing something here, but a cursory search for such a result turned up this paper http://www.icm2006.org/proceedings/Vol_III/contents/ICM_Vol_3_48.pdf, where (on page 986), it says expressing the determinant as a permanent of dimension $O(n)$ is easy and the converse is open. Am I missing something here?
Nikhil
CC BY-SA 3.0
2013-02-15T14:42:52.253Z
@Ramprasad Oops! I tried working out the reduction, and I take back my previous claim - I misread the reduction mentioned in the paper I linked in my last comment. I don't think it is a projection, and might yield a circuit of higher depth or introduces more variables!
Nikhil
CC BY-SA 3.0
2013-02-15T14:49:00.630Z
I'm fairly sure that is a typo/error in the article (but I shall check with Manindra though). Avi Wigderson's [talk](http://www.math.ias.edu/~avi/TALKS/Valiant_Lecture.ppt) (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
CC BY-SA 3.0
2013-02-15T15:26:09.897Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/7519/discussion-between-ramprasad-and-nikhil)
Ramprasad
CC BY-SA 3.0
2013-05-10T11:37:20.750Z
Curious: If $2^{\omega(f(n)}$ lower bound for DET yields a $2^{\omega(q^{-1}(f(n))}$ lower bound for PERM at depth 3, then since we have $2^{n^{\frac{1}{2}+\epsilon}}$ upper bound for DET over complex numbers (from chasm at depth $3$), we will not have a $2^{n^{\frac{1}{2}+\epsilon}}$ lower bound for PERM if $q(n) = O(n^{1+\delta})$ for some $\delta > 0$? Even if $q(n) = O(n)$, will we not achieve a $2^{n^{\frac{1}{2}+\epsilon}}$  lower bound for PERM if the lower bound for DET over cmplex is shown to be $2^{n^{\frac{1}{2}}}$? What if the $2^{n^{\frac{1}{2}}}$ lower bound for DET is tight?
Turbo
CC BY-SA 3.0
2013-02-15T04:13:01.747Z
2013-02-18T16:19:52.713Z
2013-02-18T16:19:52.713Z
Joshua Grochow
<p>In light of the recent <a href="http://eccc.hpi-web.de/report/2013/026/">chasm at depth-3</a> 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 <a href="http://www.google.co.in/url?sa=t&amp;rct=j&amp;q=grigoriev%20karpinski%20%20an%20exponential%20lower%20bound%20for%20depth%203&amp;source=web&amp;cd=1&amp;cad=rja&amp;ved=0CC4QFjAA&amp;url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.2768&amp;ei=szodUY_yF8L-rAfD_YDYCg&amp;usg=AFQjCNFgR3k4wXZyeUQVgqXgh81Rf38QBw&amp;bvm=bv.42452523,d.bmk">proved</a> 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). <a href="http://en.wikipedia.org/wiki/Computing_the_permanent#Ryser_formula">Ryser's formula</a> 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:</p>

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

<p>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).</p>

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

CC BY-SA 3.0
2013-02-15T00:05:12.510Z
That's interesting.... recently (http://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
CC BY-SA 3.0
2013-02-15T04:01:17.987Z
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
CC BY-SA 3.0
2014-06-05T15:31:18.460Z
Are there similar/any lower bound known for determinant/permanent in case of depth 3 circuits over fields of characteristic zero?
Gorav Jindal
CC BY-SA 3.0
2014-06-08T08:33:43.103Z
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 http://www.cs.technion.ac.il/~shpilka/publications/ShpilkaWigderson_d3-circuits.ps.gz
Nikhil
<circuit-complexity><lower-bounds><permanent><arithmetic-circuits><determinant>
Lower bound for determinant and permanent
Nikhil
# Lower bound for determinant and permanent

(Asked by: username_0 on 2013-02-14)

In light of the recent [chasm at depth-3](http://eccc.hpi-web.de/report/2013/026/) 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](http://www.google.co.in/url?sa=t&rct=j&q=grigoriev%20karpinski%20%20an%20exponential%20lower%20bound%20for%20depth%203&source=web&cd=1&cad=rja&ved=0CC4QFjAA&url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.2768&ei=szodUY_yF8L-rAfD_YDYCg&usg=AFQjCNFgR3k4wXZyeUQVgqXgh81Rf38QBw&bvm=bv.42452523,d.bmk) 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](http://en.wikipedia.org/wiki/Computing_the_permanent#Ryser_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.

**Tags:** circuit-complexity, lower-bounds, permanent, arithmetic-circuits, determinant

> **Comments:**
> **username_1**: That's interesting.... recently (http://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...  
> **username_0**: 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.  
> **username_2**: Are there similar/any lower bound known for determinant/permanent in case of depth 3 circuits over fields of characteristic zero?  
> **username_0**: 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 http://www.cs.technion.ac.il/~shpilka/publications/ShpilkaWigderson_d3-circuits.ps.gz  

---

## 2 answers

### Answer by username_6 on 2013-02-15. Score: 11 | Accepted answer

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

> **Comments:**
> **username_7**: 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.  
> **username_0**: @username_7: 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?  
> **username_7**: @username_0: 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.  
> **username_0**: @username_7: I think I am definitely missing something here, but a cursory search for such a result turned up this paper http://www.icm2006.org/proceedings/Vol_III/contents/ICM_Vol_3_48.pdf, where (on page 986), it says expressing the determinant as a permanent of dimension $O(n)$ is easy and the converse is open. Am I missing something here?  
> **username_0**: @username_7 Oops! I tried working out the reduction, and I take back my previous claim - I misread the reduction mentioned in the paper I linked in my last comment. I don't think it is a projection, and might yield a circuit of higher depth or introduces more variables!  
> **username_7**: I'm fairly sure that is a typo/error in the article (but I shall check with Manindra though). Avi Wigderson's [talk](http://www.math.ias.edu/~avi/TALKS/Valiant_Lecture.ppt) (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!  
> **username_7**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/7519/discussion-between-ramprasad-and-nikhil)  
> **username_8**: Curious: If $2^{\omega(f(n)}$ lower bound for DET yields a $2^{\omega(q^{-1}(f(n))}$ lower bound for PERM at depth 3, then since we have $2^{n^{\frac{1}{2}+\epsilon}}$ upper bound for DET over complex numbers (from chasm at depth $3$), we will not have a $2^{n^{\frac{1}{2}+\epsilon}}$ lower bound for PERM if $q(n) = O(n^{1+\delta})$ for some $\delta > 0$? Even if $q(n) = O(n)$, will we not achieve a $2^{n^{\frac{1}{2}+\epsilon}}$  lower bound for PERM if the lower bound for DET over cmplex is shown to be $2^{n^{\frac{1}{2}}}$? What if the $2^{n^{\frac{1}{2}}}$ lower bound for DET is tight?  

---

### Answer by username_3 on 2013-02-16. Score: 11

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.

> **Comments:**
> **username_4**: I removed the advertisement.  
> **username_5**: Can you give the reference for the proof?  

---

