<p>The place from which I had read the proof was <a href="http://math-www.uni-paderborn.de/agpb/work/habil.ps">Completeness and Reduction in Algebraic Complexity Theory by Peter Bürgisser (.ps)</a>. As for the determinental complexity of the permanent, the best lower bound known so far is $\Omega(n^2)$ by <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.4910&amp;rep=rep1&amp;type=pdf">Mignon and Ressayre</a>. </p>

CC BY-SA 3.0
2013-09-26T14:40:41.887Z
Jin Yi Cai et al have extended Mignon's result to char $p$. The basic idea is to consider Hessian but specific matrices differ.
Turbo
CC BY-SA 3.0
2013-09-26T19:06:42.050Z
Landsberg, Manivel, and Ressayre (http://arxiv.org/abs/1004.4802) have also extended the Mignon--Ressayre result from determinantal complexity to border-determinantal complexity. (The LMR paper is fairly advanced from this point of view, but I thought I should at least mention that it was out there.)
Joshua Grochow
CC BY-SA 3.0
2013-09-26T09:02:15.343Z
2013-09-26T09:02:15.343Z
Ramprasad
<p>Can some one suggest a good source for VNP completeness of Permanent. I tried reading it from book on Algebraic complexity theory by Burgisser,clausen,shokrollahi,lickteig. 
And What is the best known lower-bound on determinental complexity of $PERM_{n}$? </p>

<cc.complexity-theory><arithmetic-circuits>
VNP completeness of Permanent
Tulasi
# VNP completeness of Permanent

(Asked by: username_0 on 2013-09-26)

Can some one suggest a good source for VNP completeness of Permanent. I tried reading it from book on Algebraic complexity theory by Burgisser,clausen,shokrollahi,lickteig.
And What is the best known lower-bound on determinental complexity of $PERM\_{n}$?

**Tags:** cc.complexity-theory, arithmetic-circuits

---

## 1 answers

### Answer by username_1 on 2013-09-26. Score: 6 | Accepted answer

The place from which I had read the proof was [Completeness and Reduction in Algebraic Complexity Theory by Peter Bürgisser (.ps)](http://math-www.uni-paderborn.de/agpb/work/habil.ps). As for the determinental complexity of the permanent, the best lower bound known so far is $\Omega(n^2)$ by [Mignon and Ressayre](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.4910&rep=rep1&type=pdf).

> **Comments:**
> **username_2**: Jin Yi Cai et al have extended Mignon's result to char $p$. The basic idea is to consider Hessian but specific matrices differ.  
> **username_3**: Landsberg, Manivel, and Ressayre (http://arxiv.org/abs/1004.4802) have also extended the Mignon--Ressayre result from determinantal complexity to border-determinantal complexity. (The LMR paper is fairly advanced from this point of view, but I thought I should at least mention that it was out there.)  

---

